2次元imos法
imos法は,高次元に拡張することができる.ここでは,2次元imos法を説明する.2次元配列の横の長さを\(W\),縦の長さを\(H\)とする.
- 矩形範囲更新: \(O(1)\)
- 2次元配列上の各要素の値の取得\(O(HW)\)
2次元配列の各要素は可換群を成す集合の要素である必要がある.
説明
考え方は1次元のimos法と同じである.2次元imos法では,\((l_x, l_y)\)を左上の座標,\((r_x, r_y)\)を右下とするような矩形(\((l_x, l_y)\)は矩形内,\((r_x, r_y)\)は矩形外の座標)に値\(x\)を作用させる場合,\(l_x, l_y\)に\(x\)を,\(r_x, l_y\)に\(x^{-1}\)を,\(l_x, r_y\)に\(x^{-1}\)を,\(r_x, r_y\)に\(x\)を作用させる.実際の値を得るには,各行ごとに左から累積値を取った後に,各列ごとに上から累積値を取れば良い.
コード
template <class S, S (*op)(S, S), S (*e)(), S (*inv)(S)> struct Imos2D {
private:
vector<vector<S>> v;
public:
Imos2D(int h, int w) { v.assign(h+1, vector<S>(w+1, e())); }
void query(int lx, int ly, int rx, int ry, S x) { // [(lx, ly), (rx, ry))
v[lx][ly] = op(v[lx][ly], x);
v[rx][ly] = op(v[rx][ly], inv(x));
v[lx][ry] = op(v[lx][ry], inv(x));
v[rx][ry] = op(v[rx][ry], x);
}
vector<vector<S>> get_values() {
for (vector<S> &vv: v) rep (i, 1, vv.size())
vv[i] = op(vv[i-1], vv[i]);
rep (j, v[0].size()) rep (i, 1, v.size())
v[i][j] = op(v[i-1][j], v[i][j]);
return move(v);
}
};