英語で書きましたが、ぎりぎりエスパーできるくらいの難易度を目指しました。 問題文に書いてあることをざっくりまとめると、『NNN 個の整数 A1...ANA_1 ... A_NA1...AN が与えられ、各クエリで AX,AX+1...AY−1,AYA_X, A_{X+1} ... A_{Y-1}, A_YAX,AX+1...AY−1,AY の合計を求める』となります。 AAA の累積和を取り、各クエリで AY−AX−1A_Y - A_{X-1}AY−AX−1 を求めることでこの問題を解くことができます。