配列の長さをNとした時
連続区間の和を求めるクエリを
前処理:O(N)
クエリ:O(1)
で求めることができる。

例
配列Aの長さを10とする。
各配列内の値を
A={1,2,3,4,5,6,7,8,9,10}
とする。
A[1] = 1,A[9] = 9。

累積和の配列Bは、
Bの各要素の初期値を0として、
以下のように構築される

B[1] = A[1];//B[0]=0とすればB[1]=A[1]+B[0]でもOK:index問題。
for(int i=2;i<=10;i = i + 1 ){
	B[i] = A[i] + B[i-1];
}

配列Bの意味は
B[i]:配列Aの1番目からi番目の和

実際に手順を追ってみる。
配列Aは変わらないので,配列Bを追う。
初期値
A={1,2,3,4,5,6,7,8,9,10}
B={0,0,0,0,0,0,0,0,0,0}

B[1] = A[1] = 1
B={1,0,0,0,0,0,0,0,0,0}

B[2] = A[2] + B[1] = 2 + 1 = 3
B={1,3,0,0,0,0,0,0,0,0}

B[3] = A[3] + B[2] = 3 + 3 = 6
B={1,3,6,0,0,0,0,0,0,0}

B[4] = A[4] + B[3] = 4 + 6 = 10
B={1,3,6,10,0,0,0,0,0,0}

B[5] = A[5] + B[4] = 5 + 10 = 15
B={1,3,6,10,15,0,0,0,0,0}

B[6] = A[6] + B[5] = 6 + 15 = 21
B={1,3,6,10,15,21,0,0,0,0}

B[7] = A[7] + B[6] = 7 + 21 = 28
B={1,3,6,10,15,21,28,0,0,0}

B[8] = A[8] + B[7] = 8 + 28 = 36
B={1,3,6,10,15,21,28,36,0,0}

B[9] = A[9] + B[8] = 9 + 36 = 45
B={1,3,6,10,15,21,28,36,45,0}

B[10] = A[10] + B[9] = 10 + 45 = 55
B={1,3,6,10,15,21,28,36,45,55}

Aの累積和配列Bが計算できた。


利便性
ある配列Aで、区間[L<=R]の和を求めたい時
つまり、配列AのL番目からR番目の値の和を求めたい時、
Aの累積和配列Bがあれば、
以下のように計算できる

AのLからRまでの和 = B[R] - B[L-1]

Σ_[k=L,R]A[k] = Σ_[k=1,R]A[k] - Σ[k=1,L-1]A[k]

          L     R
+ 1 2 3 4 5 6 7 8
- 1 2 3 4
=         5 6 7 8

Aにおける1番目の要素からi番目までの累積和が分かれば、
Aにおける連続区間の和がO(1)で計算できる。
その累積和の記録が配列B

ナイーブな実装では
LからRまでの和を計算するのに(R-L+1)回の加算が必要になる。

注意点としては
配列Aは変更されないという点。
元の配列Aに変更があった時には、
累積和配列Bも変更する必要がある。
その場合には、BITなど他のデータ構造の使用を考えた方が良い。
(BITだとこれぐらい？:前処理(O(N)||O(NlogN)),更新O(logN),クエリO(logN))

累積和の発展として
imos法
一次元いもす法
二次元Imos法

データ構造の発展として
BIT
segment-tree
セグメントツリー