題目連結：
題目大意：
輸入第一列給定一正整數 n（1 ≦ n ≦ 10 ^ 6），代表現在有 n 個數。第二列輸入 n 個整數 a1 、 a2 、 …… 、an（|ai| ≦ 10 ^ 6），即為這 n 個數的內容。
接著的第三列給定一正整數 q（1 ≦ q ≦ 10 ^ 6），代表有 q 筆詢問。接著 q 列輸入，每列給定兩正整數 L 、 R（1 ≦ L ≦ R ≦ n），代表需要計算
之值為何並輸出（例如，L = 3 、 R = 5，則上式為 a3 × 3 + a4 × 2 + a5 × 1）。每筆輸出佔一列。
範例輸入：
5
1 2 3 4 5
5
2 4
3 5
3 3
1 5
1 2
範例輸出：
16
22
3
35
4
解題思維：
我們先觀察 L = 1 且 R 從 1 開始漸增時，所求數值的變化：
R = 1 得
a1
R = 2 得
2a1 + a2
R = 3 得
3a1 + 2a2 + a3
R = 4 得
4a1 + 3a2 + 2a3 + a4
……
我們將上面改寫一下後，可以看到
R = 1 得
a1
R = 2 得
a1 + (a1 + a2)
R = 3 得
a1 + (a1 + a2) + (a1 + a2 + a3)
R = 4 得
a1 + (a1 + a2) + (a1 + a2 + a3) + (a1 + a2 + a3 + a4)
……
如果讀者還記得前綴和（Prefix Sums，如這題）的概念的話可能會發現一些端倪。也就是說，如果我們定義
P0 = 0、
Pi = a1 + a2 + …… + ai（也就是前 i 項之和），
則可以看到上面的數列可以改寫成
R = 1 得
P1
R = 2 得
P1 + P2
R = 3 得
P1 + P2 + P3
R = 4 得
P1 + P2 + P3 + P4
……
也就是前綴和的前綴和。因此我們以下定義
Q0 = 0、
Qi = P1 + P2 + …… + Pi（即前綴和 P 的前 i 項之和）
但是實際上我們還有 L 需要考慮，也就是說大部分的時候我們會遇到像是 L = 4 、 R = 6 的情況，即 L ≠ 1。沒關係，在此例中我們可以觀察一下所求數值與 Q5 的差別：
所求數值為 3a4 + 2a5 + a6（以下稱 X），改寫一下可以得到 X =
a4 + (a4 + a5) + (a4 + a5 + a6)；
Q5 = P1 + P2 + P3 + P4 + P5 + P6，即
a1 +
(a1 + a2) +
(a1 + a2 + a3) +
(a1 + a2 + a3 + a4) +
(a1 + a2 + a3 + a4 + a5) +
(a1 + a2 + a3 + a4 + a5 + a6)
可以看到紅色標注的數字即是 Q5 中相對於所求數值多出來的數字。
我們把這些數字獨立出來一下，得 Q5 =
a1 +
(a1 + a2) +
(a1 + a2 + a3) +
(a1 + a2 + a3) +
(a1 + a2 + a3) +
(a1 + a2 + a3)
X
可以看到 (a1 + a2 + a3) 這個項次（可以看到剛好是 P3）重複了四次，而且前三項實際上可以看作是 Q3。因此我們將 Q5 減去 Q3，得到
(a1 + a2 + a3) +
(a1 + a2 + a3) +
(a1 + a2 + a3) +
X
可以看到剩下了 3 倍的 P3，因此我們將 Q5 再減去 3P3 便只會留下 X。
再觀察一個例子，這次 L = 5 、 R = 10：
所求數值為 6a5 + 5a6 + 4a7 + 3a8 + 2a9 + a10（以下稱為 Y）。而 Q10 =
P1 + P2 + P3 + P4 + P5 + P6 + P7 + P8 + P9 + P10
各項展開後並將不要的項次獨立可得 Q10 =
a1 +
(a1 + a2) +
(a1 + a2 + a3) +
(a1 + a2 + a3 + a4) +
(a1 + a2 + a3 + a4) +
(a1 + a2 + a3 + a4) +
(a1 + a2 + a3 + a4) +
(a1 + a2 + a3 + a4) +
(a1 + a2 + a3 + a4) +
(a1 + a2 + a3 + a4) +
Y
而其中前四項即為 Q4 而 (a1 + a2 + a3 + a4)（也就是 P4），則額外（不包含 Q4 中那一次）多重複了六次（也就是 R - L + 1 次）。
因此我們將 Q10 減去 Q4 以及 6P4 即可得到 Y。
此時我們將上面的觀察推廣之後可以得到，所求數值實際上就是
QR - QL-1 - (R - L + 1) × PL-1
因此我們在輸入 a1 、 a2 、 …… 、an 之後，求出前綴和 P 與前綴和的前綴和 Q。其後對於每一筆詢問 (L, R)，我們便可以在 O(1) 時間內得到所求。不過值得注意的是本題數字不小，求總和的時候可能會超過 2 ^ 31 - 1。因此，對於 C++ 等有變數大小限制之語言，應使用 long long 等可以容納較大數值之型態。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
