ei1333's page

ホーム > Wiki

二次元累積和

説明

点add, 矩形sumの $2$ 次元の累積和。前計算として事前に累積させておけば, 累積和を $O(1)$ で求めることが出来る。

使い方

計算量

実装例

template< class T >
struct CumulativeSum2D
{
  vector< vector< T > > data;

  CumulativeSum2D(int W, int H) : data(W + 1, vector< int >(H + 1, 0)) {}

  void add(int x, int y, int z)
  {
    ++x, ++y;
    if(x >= data.size() || y >= data[0].size()) return;
    data[x][y] += z;
  }

  void build()
  {
    for(int i = 1; i < data.size(); i++) {
      for(int j = 1; j < data[i].size(); j++) {
        data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
      }
    }
  }

  T query(int sx, int sy, int gx, int gy)
  {
    return (data[gx][gy] - data[sx][gy] - data[gx][sy] + data[sx][sy]);
  }
};

問題例

参考資料