TOP > 動的計画法 二次元累積和(Cumulative-Sum-2D) 2018/08/30 • ei1333 説明 $2$ 次元の累積和。前計算として事前に累積和をとることで, 矩形和を $O(1)$ で求めることが出来る。 計算量 構築 $O(WH)$ クエリ $O(1)$ 実装例 add($x$, $y$, $z$): 要素 $($x$, $y$)$ に値 $z$ を加える build(): 累積和を構築する query($sx$, $sy$, $gx$, $gy$): 左下 $(sx, sy)$, 右上 $(gx, gy)$ の矩形内の和を求める(半開区間で与えることに注意すること。具体的には列 $gx$ と行 $gy$ は含まない) 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, T 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]); } };