二维树状数组

二维树状数组

二维树状数组是用于维护 二维表信息 的一种数据结构，这样的信息也需要具有 结合律 和 可差分性。

比如要实现二维表的 单点修改 与 子矩阵和查询。

单点修改与子矩阵查询

子矩阵查询

对于子矩阵和查询，可以参照 二维前缀和 中的子矩阵和查询。

规定 $sum[i][j]$ 表示以 $(1,1)$ 为左上角，以 $(i,j)$ 为右下角的子矩阵和，称 $(i,j)$ 的 前缀和，之后不再赘述。

那么求以 $(x_1,y_1)$ 为左上角，以 $(x_2,y_2)$ 为右下角的子矩阵和则可以写成若干前缀和的组合：
$$sum[x_2][y_2]-sum[x_2][y_1-1]-sum[x_1-1][y_2]+sum[x_1-1][y_1-1]$$
所以维护子矩阵和就等价于维护 矩阵的前缀和。

而要查询 $(i,j)$ 的前缀和，可以仿照一维树状数组，适当地对每个位置进行 信息压缩。

对于 $i$，设其 二进制拆分 为 $2^{k_1}+2^{k_2}+\cdots +2^{k_m}(k_1<k_2<\cdots <k_m)$。

所以 $1\sim i$ 行的信息可以 被压缩 为 $m$ 块信息。

$tree[i]$ 就维护一个大小为 $2^{k_1}$ 的 连续行信息，此时剩下 $m-1$ 块。

不妨设 $j=i-2^{k_1}$，则 $j$ 的二进制拆分为 $2^{k_2}+\cdots +2^{k_m}(k_2<\cdots <k_m)$，

所以 $tree[j]$ 就维护一个大小为 $2^{k_2}$ 的连续行信息，此时剩下 $m-2$ 块。

以此类推…

此时得到了第一个 状态设计，就是 $tree[i]$ 维护以 $i$ 行结尾的大小为 $lowbit(i)$ 的连续行信息。

这样的话如果要查询 $(i,j)$ 的前缀和，那么行只需要遍历 $log(i)$ 次。

此时列仍没被压缩，所以每一列仍然需要 $m$ 次遍历。

所以考虑 对列进行二进制拆分，过程与行类似。

此时得到了最终的状态设计，$tree[i][j]$ 维护以 $i$ 结尾的连续 $lowbit(i)$ 行且以 $j$ 结尾的连续 $lowbit(j)$ 列的子矩阵信息。

故要查询 $(i,j)$ 的前缀和，行只需要遍历 $log(i)$ 次，列只需要遍历 $log(j)$ 次。

故一次查询的时间复杂度是 $O(lo{g}^{2}n)$。

单点修改

如果要修改 $(x,y)$ 的值，那么就需要修改 所有能管辖到 $(x,y)$ 的位置。

对于行而言，能管辖到第 $x$ 行的 最小位置 是 $x$，同理，能管辖到第 $y$ 列的 最小位置 是 $y$。

所以能管辖到 $(x,y)$ 的 最小位置 是 $tree[x][y]$。

在二维树状数组中，对于 任意一个 能管辖到 $(x,y)$ 的位置 $(x+t,y+z)$，我们如何能找到这个位置？

这个问题可以转换为两个一维树状数组上的问题。

对于行而言，如果 $x+t$ 能管辖到 $x$，是否 $x+t$ 一定能被 $x$ 不断跳 $lowbit$ 到达？

这个问题是肯定的，证明可以见 树状数组的性质 这一篇。

所以我们只需要从 $(x,y)$ 开始，不断跳 $lowbit$ 就能到达所有的管辖 $(x,y)$ 的位置。

template<typename T>
struct Fenwick2D {int n, m;vector <vector<T>> tree;Fenwick2D(int _n, int _m) {n = _n;m = _m;tree.assign(n + 1, vector<T>(m + 1));}int lowbit (int x) {return x & (-x);}// 单点加 vvoid add(int x, int y, T v) {for (int i = x; i <= n; i += lowbit(i)) {for (int j = y; j <= m; j += lowbit(j)) {tree[i][j] += v;}}}// 求(x, y)前缀和T get_pre_sum(int x, int y) {T ans = 0;for (int i = x; i; i -= lowbit(i)) {for (int j = y; j; j -= lowbit(j)) {ans += tree[i][j];}}return ans;}// 求子矩阵和T get_range_sum(int x1, int y1, int x2, int y2) {return get_pre_sum(x2, y2) - get_pre_sum(x1 - 1, y2)- get_pre_sum(x2, y1 - 1) + get_pre_sum(x1 - 1, y1 - 1);}
};

子矩阵加与子矩阵查询

子矩阵加

现在要给以 $(x_1,y_1)$ 为左上角，$(x_2,y_2)$ 为右下角的子矩阵都加上 $v$，依旧可以往差分方向去考虑。

而 二维差分数组 $d[i][j]$ 的定义是什么呢？

不妨参考一维差分数组，我们都知道差分的目的是 高效地 为了给一段区间加上相同的数。

且差分的前 $i$ 项和恰好等于原序列的第 $i$ 项，故有
$$a[i]=\sum _{j=1}^{i}d[j]$$
又因为
$$\begin{array}{rl}a[i]& =\sum _{j=1}^{i}d[j]=\sum _{j=1}^{i-1}d[j]+d[i]=a[i-1]+d[i]\end{array}$$
所以有
$$d[i]=a[i]-a[i-1]$$
等价替换，我们希望二维差分数组的前缀和满足
$$a[i][j]=\sum _{k=1}^i\sum _{t=1}^{j}d[k][t]$$
而式子可以变形为
$$\begin{array}{rl}a[i][j]& =\sum _{k=1}^i\sum _{t=1}^{j}d[k][t]\\ & =\sum _{k=1}^{i-1}\sum _{t=1}^{j}d[k][t]+\sum _{k=1}^i\sum _{t=1}^{j-1}d[k][t]-\sum _{k=1}^{i-1}\sum _{t=1}^{j-1}d[k][t]+d[i][j]\\ & =a[i-1][j]+a[i][j-1]-a[i-1][j-1]+d[i][j]\end{array}$$
所以有
$$d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]$$
此时我们得到了 二维差分数组的定义。

接下来思考，应该怎么样对差分数组操作才能实现给子矩阵加上同一个数？

若我们给 $d[x_1][y_1]$ 增加 $v$，$d[x_1][y_1]$ 的增加会影响所有满足 $i\ge x_1,j\ge y_1$ 的位置 $a[i][j]$。

而我们希望这个增加的值影响只限定在 $x_1\le i\le x_2,y_1\le j\le y_2$ 范围内。

所以我们需要在 $d[x_2+1][y_1]$ 处加上 $-v$，这能阻止 $(x_2+1,y_1)$ 及其右下方被影响。

我们还需要在 $d[x_1][y_2+1]$ 处加上 $-v$，这能阻止 $(x_1,y_2+1)$ 及其右下方被影响。

但是可以发现 $(x_2+1,y_2+1)$ 及其右下方被阻止了两次，所以还需要抵消一次阻止。

故在 $d[x_2+1][y_2+1]$ 处加上 $v$。

所以，子矩阵的修改变成了四次单点修改。
$$\begin{array}{r}d[x_1][y_1]+v,d[x_2+1][y_1]-v,d[x_1][y_2+1]-v,d[x_2+1][y_2+1]+v\end{array}$$

子矩阵和

由于要进行子矩阵加，所以我们维护的是原数组的二维差分数组。子矩阵和可以转换为若干的前缀和的组合。

而 $(x,y)$ 的前缀和表示为
$$\begin{array}{rl}sum[x][y]& =\sum _{i=1}^x\sum _{j=1}^{y}a[i][j]\\ & =\sum _{i=1}^x\sum _{j=1}^y(\sum _{k=1}^i\sum _{t=1}^{j}d[k][t])\end{array}$$
考虑化简（记忆化简的式子可以用打表的方式）：

对于 $a[x][y]$ 来说，它的表达式里 $d[1][1]\sim d[x][y]$ 每个数都出现了一次。

对于 $a[x][y-1]$ 来说，它的表达式里 $d[1][1]\sim d[x][y-1]$ 每个数都出现了一次。

而 $sum[x][y]$ 的表达式里 $a[x][y]$ 与 $a[x][y-1]$ 只出现了一次。

所以在 $sum[x][y]$ 的表达式里中，$d[x][y]$ 出现了一次，$d[x][y-1]$ 出现了两次。

以此类推 $d[x][j]$ 出现了 $y-j+1$ 次，同理 $d[i][y]$ 出现了 $x-i+1$ 次。

故 $d[i][j]$ 出现了 $(x-i+1)\times (y-j+1)$ 次。

则有
$$\begin{array}{rl}sum[x][y]& =\sum _{i=1}^x\sum _{j=1}^{y}d[i][j]\times (x-i+1)\times (y-j+1)\\ & =\sum _{i=1}^x\sum _{j=1}^y(d[i][j]\times (xy-yi+y-xj+ij-j+x-i+1))\\ & =\sum _{i=1}^x\sum _{j=1}^y(d[i][j]\times (xy-(y+1)i-(x+1)j+ij+x+y+1))\\ & =(xy+x+y+1)\sum _{i=1}^x\sum _{j=1}^{y}d[i][j]-(y+1)\sum _{i=1}^x\sum _{j=1}^{y}i\times d[i][j]-(x+1)\sum _{i=1}^x\sum _{j=1}^{y}j\times d[i][j]\\ & +\sum _{i=1}^x\sum _{j=1}^{y}ij\times d[i][j]\end{array}$$
所以我们需要维护 $4$ 个树状数组来维护这个式子，分别是 tree，tree_i，tree_j，tree_ij。

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18template<typename T>
struct Fenwick2D {int n, m;vector <vector<T>> tree, tree_i, tree_j, tree_ij;Fenwick2D(int _n, int _m) {n = _n;m = _m;tree.assign(n + 2, vector<T>(m + 2));tree_i.assign(n + 2, vector<T>(m + 2));tree_j.assign(n + 2, vector<T>(m + 2));tree_ij.assign(n + 2, vector<T>(m + 2));}int lowbit (int x) {return x & (-x);}void add(int x, int y, T v) {for (int i = x; i <= n; i += lowbit(i)) {for (int j = y; j <= m; j += lowbit(j)) {tree[i][j] += v;tree_i[i][j] += i*v;tree_j[i][j] += j*v;tree_ij[i][j] += i*j*v;}}}void add_range(int x1, int y1, int x2, int y2, T v) {add(x1, y1, v);add(x2 + 1, y1, - v);add(x1, y2 + 1, -v);add(x2 + 1, y2 + 1, v);}T get_pre_sum(int x, int y) {T ans = 0, ans_i = 0, ans_j = 0, ans_ij = 0;for (int i = x; i; i -= lowbit(i)) {for (int j = y; j; j -= lowbit(j)) {ans += tree[i][j];ans_i += tree_i[i][j];ans_j += tree_j[i][j];ans_ij += tree_ij[i][j];}}ans *= (x * y + x + y + 1);ans_i *= (y + 1);ans_j *= (x + 1);return ans - ans_i - ans_j + ans_ij;}T get_range_sum(int x1, int y1, int x2, int y2) {return get_pre_sum(x2, y2) - get_pre_sum(x1 - 1, y2)- get_pre_sum(x2, y1 - 1) + get_pre_sum(x1 - 1, y1 - 1);}};
void slove () {Fenwick2D<int> tree(5, 6);
}signed main () {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);slove();
}