累積和
ある数列$ a_nの各要素までの累積的な和を要素とする数列$ S_i = \scriptstyle\sum_{k = 1}^i a_kのこと。特定の連続する部分列の和を$ O(1)で求められる。
累積和のサイズは元の数列と同じサイズになるが、計算の都合上、$ 1始まりにしておくと計算しやすい。また、そのときにもとの数列$ Aも1始まりにしておくと混乱が少ない。
1次元の場合
code:java
intN + 1 A; // Aは1始まりの長さNの数列 intN + 1 S; // S_iはA_1からA_iまでの総和 for (int i = 1; i <= N; i++) Si = Si - 1 + Ai; 2次元の場合
code:java
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
}
}
3次元の場合
code:java
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
for (int k = 1; k <= N; k++) {
}
}
}