Loading [Contrib]/a11y/accessibility-menu.js
$\newcommand{\O}{\mathrm{O}}$ My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

BIT 2D RangeAdd RangeSum

コードについての説明(個人的メモ)

多次元領域の範囲加算および範囲総和のクエリに $\O( \mathrm{polylog} n)$ で答えるデータ構造(実装は2次元).
元論文は "A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays" [Mishra 2013]

時間計算量は $n \times n$ の正方形について 加算クエリ: $16 \log^2 n$ 総和クエリ: $16 \log^2 n$
具体的には $d$ 次元について計算量は $\O (4^d \log^d n)$

コード

  1. template<typename T> class BIT_2D_RangeAdd_RangeSum {
  2. private:
  3.     const int n, m;
  4.     vector<vector<T> > bitxy, bitx, bity, bitc;
  5.     void add(const int i, const int j, const T valxy, const T valx, const T valy, const T valc){
  6.         for(int i_ = i+1; i_ < n; i_ += i_ & -i_)
  7.             for(int j_ = j+1; j_ < m; j_ += j_ & -j_)
  8.                 bitxy[i_][j_] += valxy, bitx[i_][j_] += valx, bity[i_][j_] += valy, bitc[i_][j_] += valc;
  9.     }
  10.     // [0, i] x [0, j]
  11.     T sum(const int i, const int j){
  12.         T s = 0;
  13.         for(int i_ = i+1; i_ > 0; i_ -= i_ & -i_)
  14.             for(int j_ = j+1; j_ > 0; j_ -= j_ & -j_)
  15.                 s += bitxy[i_][j_] * i * j + bitx[i_][j_] * i + bity[i_][j_] * j + bitc[i_][j_];
  16.         return s;
  17.     }
  18. public:
  19.     BIT_2D_RangeAdd_RangeSum(const int sz1, const int sz2) : n(sz1 + 1), m(sz2 + 1),
  20.             bitxy(n, vector<T>(m, 0)), bitx(n, vector<T>(m, 0)), bity(n, vector<T>(m, 0)), bitc(n, vector<T>(m, 0)){}
  21.     // [lx, rx)×[ly, ry) に val を足す
  22.     void add(const int lx, const int ly, const int rx, const int ry, const T val){
  23.         add(lx, ly, val, -val * (ly - 1), -val * (lx - 1), val * (lx - 1) * (ly - 1));
  24.         add(rx, ly, -val, val * (ly - 1), val * (rx - 1), -val * (rx - 1) * (ly - 1));
  25.         add(lx, ry, -val, val * (ry - 1), val * (lx - 1), -val * (lx - 1) * (ry - 1));
  26.         add(rx, ry, val, -val * (ry - 1), -val * (rx - 1), val * (rx - 1) * (ry - 1));
  27.     }
  28.     // [lx, rx)×[ly, ry) の和を求める
  29.     T sum(const int lx, const int ly, const int rx, const int ry){
  30.         return sum(rx - 1, ry - 1) - sum(lx - 1, ry - 1) - sum(rx - 1, ly - 1) + sum(lx - 1, ly - 1);
  31.     }
  32.     void print(){
  33.         for(int i = 0; i < n-1; ++i){
  34.             for(int j = 0; j < m-1; ++j){
  35.                 cout << sum(i, j, i+1, j+1) << " ";
  36.             }
  37.             cout << endl;
  38.         }
  39.     }
  40. };

verify 用の問題

LibreOJ : 二维树状数组 3：区间修改，区间查询 提出コード