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);
  }
};