二维树状数组
封装一：该版本不能同时进行区间修改+区间查询。无离散化版本的空间占用为 \(\mathcal O(NM)\) 、建树复杂度为 \(\mathcal O(NM)\) 、单次查询复杂度为 \(\mathcal O(\log N\cdot \log M)\) 。
struct BIT_2D {int n, m;vector<vector<int>> w;BIT_2D(int n, int m) : n(n), m(m) {w.resize(n + 1, vector<int>(m + 1));}void add(int x, int y, int k) {for (int i = x; i <= n; i += i & -i) {for (int j = y; j <= m; j += j & -j) {w[i][j] += k;}}}void add(int x, int y, int X, int Y, int k) { // 区块修改：二维差分X++, Y++;add(x, y, k), add(X, y, -k);add(X, Y, k), add(x, Y, -k);}int ask(int x, int y) { // 单点查询int ans = 0;for (int i = x; i; i -= i & -i) {for (int j = y; j; j -= j & -j) {ans += w[i][j];}}return ans;}int ask(int x, int y, int X, int Y) { // 区块查询：二维前缀和x--, y--;return ask(X, Y) - ask(x, Y) - ask(X, y) + ask(x, y);}
};
封装二：该版本支持全部操作。但是时空复杂度均比上一个版本多 \(4\) 倍。
struct BIT_2D {int n, m;vector<vector<int>> b1, b2, b3, b4;BIT_2D(int n, int m) : n(n), m(m) {b1.resize(n + 1, vector<int>(m + 1));b2.resize(n + 1, vector<int>(m + 1));b3.resize(n + 1, vector<int>(m + 1));b4.resize(n + 1, vector<int>(m + 1));}void add(auto &w, int x, int y, int k) { // 单点修改for (int i = x; i <= n; i += i & -i) {for (int j = y; j <= m; j += j & -j) {w[i][j] += k;}}}void add(int x, int y, int k) { // 多了一步计算add(b1, x, y, k);add(b2, x, y, k * (x - 1));add(b3, x, y, k * (y - 1));add(b4, x, y, k * (x - 1) * (y - 1));}void add(int x, int y, int X, int Y, int k) { // 区块修改：二维差分X++, Y++;add(x, y, k), add(X, y, -k);add(X, Y, k), add(x, Y, -k);}int ask(auto &w, int x, int y) { // 单点查询int ans = 0;for (int i = x; i; i -= i & -i) {for (int j = y; j; j -= j & -j) {ans += w[i][j];}}return ans;}int ask(int x, int y) { // 多了一步计算int ans = 0;ans += x * y * ask(b1, x, y);ans -= y * ask(b2, x, y);ans -= x * ask(b3, x, y);ans += ask(b4, x, y);return ans;}int ask(int x, int y, int X, int Y) { // 区块查询：二维前缀和x--, y--;return ask(X, Y) - ask(x, Y) - ask(X, y) + ask(x, y);}
};