累積和

コード例

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n = 5; // vの要素数
  vector<int> v = {3, 1, 5, 8, 2}; // 対象の配列
  vector<int> t(n + 1, 0); // 累積和を格納する配列

  for (int i = 0; i < n; i++) {
    t[i + 1] = t[i] + v[i];
  }

  cout << t[5] - t[0] << endl;  // [0, 5) => 19
  cout << t[5] - t[2] << endl;  // [2, 5) => 15
  cout << t[2] - t[2] << endl;  // [2, 2) => 0
}

解説/アルゴリズム

累積和は、 $O(N)$ の前処理を行うことによって、配列上の区間の総和を $O(1)$ で求めることができるアルゴリズム。

添字	[0]	[1]	[2]	[3]	[4]
要素	3	1	5	8	2

まず対象となる配列 v を用意する。

新しい配列 t を用意して下記の計算式で値を代入していく。

• t[0] には 0
• t[1] には v[0]
• t[2] には v[0] + v[1]
• t[3] には v[0] + v[1] + v[2]
• t[n] には v[0] + v[1] + v[2] + ... v[n - 1]

添字	[0]	[1]	[2]	[3]	[4]	[5]
計算式	0	[0]	[0]+[1]	[0]+[1]+[2]	[0]+[1]+[2]+[3]	[0]+[1]+[2]+[3]+[4]
要素	0	3	4	9	17	19

と配列に値を入れていく。

vector<int> v = {3, 1, 5, 8, 2};
vector<int> t(n + 1, 0);

for (int i = 0; i < n; i++) {
  t[i + 1] = t[i] + v[i];
}

この代入処理は上記のように $O(N)$ で記述できる。

cout << t[5] - t[0] << endl; // [0, 5) => 19
cout << t[5] - t[2] << endl; // [2, 5) => 15
cout << t[2] - t[2] << endl; // [2, 2) => 0

求めた配列 t を t[b] - t[a] のように使用すると、v[a]～ v[b-1] の値の総和を求めることができる。

添字	[0]	[1]	[2]	[3]	[4]	[5]
計算式	0	[0]	[0]+[1]	[0]+[1]+[2]	[0]+[1]+[2]+[3]	[0]+[1]+[2]+[3]+[4]
要素	0	3	4	9	17	19

たとえば t[5] - t[2] というのは、配列 v の [0]+[1]+[2]+[3]+[4] - [0]+[1] で、 [0]+[1] の部分が消えて [2]+[3]+[4] だけが残るのがわかる。

二次元累積和

#include <bits/stdc++.h>
using namespace std;

int main() {
  int w = 4;
  int h = 4;

  vector<vector<int>> v = {
    {1, 0, 0, 1},
    {1, 1, 0, 0},
    {0, 0, 0, 1},
    {0, 1, 1, 0}
  };

  vector<vector<int>> s(h + 1, vector<int>(w + 1, 0));
  for (int y = 0; y < h; y++) {
    for (int x = 0; x < w; x++) {
      s[y + 1][x + 1] = s[y + 1][x] + s[y][x + 1] - s[y][x] + v[y][x];
    }
  }

  auto f = [&](int x1, int y1, int x2, int y2) -> int {
    return s[y2][x2] - s[y2][x1] - s[y1][x2] + s[y1][x1];
  };

  cout << f(0, 0, w, h) << endl;  // 7
  cout << f(2, 1, w, h) << endl;  // 2
}

二次元累積和は、累積和の考えを二次元に拡張したもので、前処理をしている状態で (x1, y1, x2, y2) を渡すと、v[y1][x1] ～ v[y2 - 1][x2 - 1]までの矩形範囲の総和を $O(1)$ で求めることができる。

vector<vector<int>> s(h + 1, vector<int>(w + 1, 0));

一次元の場合と同じ考えで、もとの配列より一つ大きいサイズで配列を作成し、左端と上端が 0 になるように埋めておく。

for (int y = 0; y < h; y++) {
  for (int x = 0; x < w; x++) {
    s[y + 1][x + 1] = s[y + 1][x] + s[y][x + 1] - s[y][x] + v[y][x];
  }
}

左から右へ、上から下へ、値を足していく。 s[y][x]には、上にある s[y-1][x]、左にある s[y][x-1]、もとの配列にある v[y][x]を足し合わせた値を格納するのだが、左上部分が重複しているので、その重複分である s[y-1][x-1]の値分だけ引いておく必要がある。

auto f = [&](int x1, int y1, int x2, int y2) -> int {
  return s[y2][x2] - s[y2][x1] - s[y1][x2] + s[y1][x1];
};

(x1, y1)～(x2, y2) の矩形範囲は、 (0, 0)～(x2, y2) から (0, 0)～(x1, y2) と (0, 0)～(x2, y1) を引いて、重複した (0, 0)～(x1, y1) を足したものになる。