树状数组

引入

树状数组是一种支持 单点修改 和 区间查询 的，代码量小的数据结构。

普通树状数组维护的信息及运算要满足 结合律 且 可差分，如加法（和）、乘法（积）、异或等。

• 结合律：$(x\circ y)\circ z=x\circ (y\circ z)$，其中 $\circ$ 是一个二元运算符。
• 可差分：具有逆运算的运算，即已知 $x\circ y$ 和 $x$ 可以求出 $y$。

需要注意的是：

• 模意义下的乘法若要可差分，需保证每个数都存在逆元（模数为质数时一定存在）；
• 例如 $gcd$，$max$ 这些信息不可差分，所以不能用普通树状数组处理，但是：
  • 使用两个树状数组可以用于处理区间最值，见 Efficient Range Minimum Queries using Binary Indexed Trees。
  • 本页面也会介绍一种支持不可差分信息查询的，$\mathrm{\Theta }({\log }^{2}n)$ 时间复杂度的拓展树状数组。

事实上，树状数组能解决的问题是线段树能解决的问题的子集：树状数组能做的，线段树一定能做；线段树能做的，树状数组不一定可以。然而，树状数组的代码要远比线段树短，时间效率常数也更小，因此仍有学习价值。

有时，在差分数组和辅助数组的帮助下，树状数组还可解决更强的 区间加单点值 和 区间加区间和 问题。

树状数组

初步感受

先来举个例子：我们想知道 $a[1\dots 7]$ 的前缀和，怎么做？

一种做法是：$a_1+a_2+a_3+a_4+a_5+a_6+a_7$，需要求 $7$ 个数的和。

但是如果已知三个数 $A$，$B$，$C$，$A=a[1\dots 4]$ 的和，$B=a[5\dots 6]$ 的总和，$C=a[7\dots 7]$ 的总和（其实就是 $a[7]$ 自己）。你会怎么算？你一定会回答：$A+B+C$，只需要求 $3$ 个数的和。

这就是树状数组能快速求解信息的原因：我们总能将一段前缀 $[1,n]$ 拆成 不多于 $\mathbf{log}\mathbf{}\mathit{n}$ 段区间，使得这 $\log n$ 段区间的信息是 已知的。

于是，我们只需合并这 $\log n$ 段区间的信息，就可以得到答案。相比于原来直接合并 $n$ 个信息，效率有了很大的提高。

不难发现信息必须满足结合律，否则就不能像上面这样合并了。

下面这张图展示了树状数组的工作原理：

最下面的八个方块代表原始数据数组 $a$。上面参差不齐的方块（与最上面的八个方块是同一个数组）代表数组 $a$ 的上级——$c$ 数组。

$c$ 数组就是用来储存原始数组 $a$ 某段区间的和的，也就是说，这些区间的信息是已知的，我们的目标就是把查询前缀拆成这些小区间。

例如，从图中可以看出：

• $c_2$ 管辖的是 $a[1\dots 2]$；
• $c_4$ 管辖的是 $a[1\dots 4]$；
• $c_6$ 管辖的是 $a[5\dots 6]$；
• $c_8$ 管辖的是 $a[1\dots 8]$；
• 剩下的 $c[x]$ 管辖的都是 $a[x]$ 自己（可以看做 $a[x\dots x]$ 的长度为 $1$ 的小区间）。

不难发现，$c[x]$ 管辖的一定是一段右边界是 $x$ 的区间总信息。我们先不关心左边界，先来感受一下树状数组是如何查询的。

举例：计算 $a[1\dots 7]$ 的和。

过程：从 $c_7$ 开始往前跳，发现 $c_7$ 只管辖 $a_7$ 这个元素；然后找 $c_6$，发现 $c_6$ 管辖的是 $a[5\dots 6]$，然后跳到 $c_4$，发现 $c_4$ 管辖的是 $a[1\dots 4]$ 这些元素，然后再试图跳到 $c_0$，但事实上 $c_0$ 不存在，不跳了。

我们刚刚找到的 $c$ 是 $c_7,c_6,c_4$，事实上这就是 $a[1\dots 7]$ 拆分出的三个小区间，合并得到答案是 $c_7+c_6+c_4$。

举例：计算 $a[4\dots 7]$ 的和。

我们还是从 $c_7$ 开始跳，跳到 $c_6$ 再跳到 $c_4$。此时我们发现它管理了 $a[1\dots 4]$ 的和，但是我们不想要 $a[1\dots 3]$ 这一部分，怎么办呢？很简单，减去 $a[1\dots 3]$ 的和就行了。

那不妨考虑最开始，就将查询 $a[4\dots 7]$ 的和转化为查询 $a[1\dots 7]$ 的和，以及查询 $a[1\dots 3]$ 的和，最终将两个结果作差。

管辖区间

那么问题来了，$c[x](x\ge 1)$ 管辖的区间到底往左延伸多少？也就是说，区间长度是多少？

树状数组中，规定 $c[x]$ 管辖的区间长度为 $2^k$，其中：

• 设二进制最低位为第 $0$ 位，则 $k$ 恰好为 $x$ 二进制表示中，最低位的 1 所在的二进制位数；
• $2^k$（$c[x]$ 的管辖区间长度）恰好为 $x$ 二进制表示中，最低位的 1 以及后面所有 0 组成的数。

举个例子，$c_{88}$ 管辖的是哪个区间？

因为 ${88}_{(10)}={01011000}_{(2)}$，其二进制最低位的 1 以及后面的 0 组成的二进制是 1000，即 $8$，所以 $c_{88}$ 管辖 $8$ 个 $a$ 数组中的元素。

因此，$c_{88}$ 代表 $a[81\dots 88]$ 的区间信息。

我们记 $x$ 二进制最低位 1 以及后面的 0 组成的数为 $\mathrm{lowbit}(x)$，那么 $c[x]$ 管辖的区间就是 $[x-\mathrm{lowbit}(x)+1,x]$。

怎么计算 lowbit？根据位运算知识，可以得到 lowbit(x) = x & -x。

1
2
3
4
5
6
7
8

int lowbit(int x) {
  // x 的二进制中，最低位的 1 以及后面所有 0 组成的数。
  // lowbit(0b01011000) == 0b00001000
  //          ~~~~^~~~
  // lowbit(0b01110010) == 0b00000010
  //          ~~~~~~^~
  return x & -x;
}

1
2
3
4
5
6
7
8
9

def lowbit(x):
    """
    x 的二进制中，最低位的 1 以及后面所有 0 组成的数。
    lowbit(0b01011000) == 0b00001000
            ~~~~~^~~
    lowbit(0b01110010) == 0b00000010
            ~~~~~~~^~
    """
    return x & -x

区间查询

接下来我们来看树状数组具体的操作实现，先来看区间查询。

回顾查询 $a[4\dots 7]$ 的过程，我们是将它转化为两个子过程：查询 $a[1\dots 7]$ 和查询 $a[1\dots 3]$ 的和，最终作差。

其实任何一个区间查询都可以这么做：查询 $a[l\dots r]$ 的和，就是 $a[1\dots r]$ 的和减去 $a[1\dots l-1]$ 的和，从而把区间问题转化为前缀问题，更方便处理。

事实上，将有关 $l\dots r$ 的区间询问转化为 $1\dots r$ 和 $1\dots l-1$ 的前缀询问再差分，在竞赛中是一个非常常用的技巧。

那前缀查询怎么做呢？回顾下查询 $a[1\dots 7]$ 的过程：

从 $c_7$ 往前跳，发现 $c_7$ 只管辖 $a_7$ 这个元素；然后找 $c_6$，发现 $c_6$ 管辖的是 $a[5\dots 6]$，然后跳到 $c_4$，发现 $c_4$ 管辖的是 $a[1\dots 4]$ 这些元素，然后再试图跳到 $c_0$，但事实上 $c_0$ 不存在，不跳了。

我们刚刚找到的 $c$ 是 $c_7,c_6,c_4$，事实上这就是 $a[1\dots 7]$ 拆分出的三个小区间，合并一下，答案是 $c_7+c_6+c_4$。

观察上面的过程，每次往前跳，一定是跳到现区间的左端点的左一位，作为新区间的右端点，这样才能将前缀不重不漏地拆分。比如现在 $c_6$ 管的是 $a[5\dots 6]$，下一次就跳到 $5-1=4$，即访问 $c_4$。

我们可以写出查询 $a[1\dots x]$ 的过程：

• 从 $c[x]$ 开始往前跳，有 $c[x]$ 管辖 $a[x-\mathrm{lowbit}(x)+1\dots x]$；
• 令 $x\leftarrow x-\mathrm{lowbit}(x)$，如果 $x=0$ 说明已经跳到尽头了，终止循环；否则回到第一步。
• 将跳到的 $c$ 合并。

实现时，我们不一定要先把 $c$ 都跳出来然后一起合并，可以边跳边合并。

比如我们要维护的信息是和，直接令初始 $\mathrm{ans}=0$，然后每跳到一个 $c[x]$ 就 $\mathrm{ans}\leftarrow \mathrm{ans}+c[x]$，最终 $\mathrm{ans}$ 就是所有合并的结果。

1
2
3
4
5
6
7
8

int getsum(int x) {  // a[1]..a[x]的和
  int ans = 0;
  while (x > 0) {
    ans = ans + c[x];
    x = x - lowbit(x);
  }
  return ans;
}

1
2
3
4
5
6

def getsum(x):  # a[1]..a[x]的和
    ans = 0
    while x > 0:
        ans = ans + c[x]
        x = x - lowbit(x)
    return ans

树状数组与其树形态的性质

在讲解单点修改之前，先讲解树状数组的一些基本性质，以及其树形态来源，这有助于更好理解树状数组的单点修改。

我们约定：

• $l(x)=x-\mathrm{lowbit}(x)+1$。即，$l(x)$ 是 $c[x]$ 管辖范围的左端点。
• 对于任意正整数 $x$，总能将 $x$ 表示成 $s\times 2^{k+1}+2^k$ 的形式，其中 $\mathrm{lowbit}(x)=2^k$。
• 下面「$c[x]$ 和 $c[y]$ 不交」指 $c[x]$ 的管辖范围和 $c[y]$ 的管辖范围不相交，即 $[l(x),x]$ 和 $[l(y),y]$ 不相交。「$c[x]$ 包含于 $c[y]$」等表述同理。

性质 $\mathbf{1}$：对于 $\mathit{x}\mathbf{\le }\mathit{y}$，要么有 $\mathit{c}\mathbf{[}\mathit{x}\mathbf{]}$ 和 $\mathit{c}\mathbf{[}\mathit{y}\mathbf{]}$ 不交，要么有 $\mathit{c}\mathbf{[}\mathit{x}\mathbf{]}$ 包含于 $\mathit{c}\mathbf{[}\mathit{y}\mathbf{]}$。

性质 $\mathbf{2}$：$\mathit{c}\mathbf{[}\mathit{x}\mathbf{]}$ 真包含于 $\mathit{c}\mathbf{[}\mathit{x}\mathbf{+}\mathbf{lowbit}\mathbf{}\mathbf{(}\mathit{x}\mathbf{)}\mathbf{]}$。

性质 $3$：对于任意 ，有 $\mathit{c}\mathbf{[}\mathit{x}\mathbf{]}$ 和 $\mathit{c}\mathbf{[}\mathit{y}\mathbf{]}$ 不交。

有了这三条性质的铺垫，我们接下来看树状数组的树形态（请忽略 $a$ 向 $c$ 的连边）。

事实上，树状数组的树形态是 $x$ 向 $x+\mathrm{lowbit}(x)$ 连边得到的图，其中 $x+\mathrm{lowbit}(x)$ 是 $x$ 的父亲。

注意，在考虑树状数组的树形态时，我们不考虑树状数组大小的影响，即我们认为这是一棵无限大的树，方便分析。实际实现时，我们只需用到 $x\le n$ 的 $c[x]$，其中 $n$ 是原数组长度。

这棵树天然满足了很多美好性质，下面列举若干（设 $fa[u]$ 表示 $u$ 的直系父亲）：

• 。
• $u$ 大于任何一个 $u$ 的后代，小于任何一个 $u$ 的祖先。
• 点 $u$ 的 $\mathrm{lowbit}$ 严格小于 $fa[u]$ 的 $\mathrm{lowbit}$。

• 点 $x$ 的高度是 ${\log }_2\mathrm{lowbit}(x)$，即 $x$ 二进制最低位 1 的位数。

• $c[u]$ 真包含于 $c[fa[u]]$（性质 $2$）。
• $c[u]$ 真包含于 $c[v]$，其中 $v$ 是 $u$ 的任一祖先（在上一条性质上归纳）。
• $c[u]$ 真包含 $c[v]$，其中 $v$ 是 $u$ 的任一后代（上面那条性质 $u$，$v$ 颠倒）。
• 对于任意 ，若 $v^{\prime }$ 不是 $u$ 的祖先，则 $c[u]$ 和 $c[v^{\prime }]$ 不交。

• 对于任意 ，如果 $v$ 不在 $u$ 的子树上，则 $c[u]$ 和 $c[v]$ 不交（上面那条性质 $u$，$v^{\prime }$ 颠倒）。
• 对于任意 ，当且仅当 $v$ 是 $u$ 的祖先，$c[u]$ 真包含于 $c[v]$（上面几条性质的总结）。这就是树状数组单点修改的核心原理。
• 设 $u=s\times 2^{k+1}+2^k$，则其儿子数量为 $k={\log }_2\mathrm{lowbit}(u)$，编号分别为 。
  • 举例：假设 $k=3$，$u$ 的二进制编号为 ...1000，则 $u$ 有三个儿子，二进制编号分别为 ...0111、...0110、...0100。

• $u$ 的所有儿子对应 $c$ 的管辖区间恰好拼接成 $[l(u),u-1]$。
  • 举例：假设 $k=3$，$u$ 的二进制编号为 ...1000，则 $u$ 有三个儿子，二进制编号分别为 ...0111、...0110、...0100。
  • c[...0100] 表示 a[...0001 ~ ...0100]。
  • c[...0110] 表示 a[...0101 ~ ...0110]。
  • c[...0111] 表示 a[...0111 ~ ...0111]。
  • 不难发现上面是三个管辖区间的并集恰好是 a[...0001 ~ ...0111]，即 $[l(u),u-1]$。

单点修改

现在来考虑如何单点修改 $a[x]$。

我们的目标是快速正确地维护 $c$ 数组。为保证效率，我们只需遍历并修改管辖了 $a[x]$ 的所有 $c[y]$，因为其他的 $c$ 显然没有发生变化。

管辖 $a[x]$ 的 $c[y]$ 一定包含 $c[x]$（根据性质 $1$），所以 $y$ 在树状数组树形态上是 $x$ 的祖先。因此我们从 $x$ 开始不断跳父亲，直到跳得超过了原数组长度为止。

设 $n$ 表示 $a$ 的大小，不难写出单点修改 $a[x]$ 的过程：

• 初始令 $x^{\prime }=x$。
• 修改 $c[x^{\prime }]$。
• 令 $x^{\prime }\leftarrow x^{\prime }+\mathrm{lowbit}(x^{\prime })$，如果 说明已经跳到尽头了，终止循环；否则回到第二步。

区间信息和单点修改的种类，共同决定 $c[x^{\prime }]$ 的修改方式。下面给几个例子：

• 若 $c[x^{\prime }]$ 维护区间和，修改种类是将 $a[x]$ 加上 $p$，则修改方式则是将所有 $c[x^{\prime }]$ 也加上 $p$。
• 若 $c[x^{\prime }]$ 维护区间积，修改种类是将 $a[x]$ 乘上 $p$，则修改方式则是将所有 $c[x^{\prime }]$ 也乘上 $p$。

然而，单点修改的自由性使得修改的种类和维护的信息不一定是同种运算，比如，若 $c[x^{\prime }]$ 维护区间和，修改种类是将 $a[x]$ 赋值为 $p$，可以考虑转化为将 $a[x]$ 加上 $p-a[x]$。如果是将 $a[x]$ 乘上 $p$，就考虑转化为 $a[x]$ 加上 $a[x]\times p-a[x]$。

下面以维护区间和，单点加为例给出实现。

1
2
3
4
5
6

void add(int x, int k) {
  while (x <= n) {  // 不能越界
    c[x] = c[x] + k;
    x = x + lowbit(x);
  }
}

1
2
3
4

def add(x, k):
    while x <= n:  # 不能越界
        c[x] = c[x] + k
        x = x + lowbit(x)

建树

也就是根据最开始给出的序列，将树状数组建出来（$c$ 全部预处理好）。

一般可以直接转化为 $n$ 次单点修改，时间复杂度 $\mathrm{\Theta }(n\log n)$（复杂度分析在后面）。

比如给定序列 $a=(5,1,4)$ 要求建树，直接看作对 $a[1]$ 单点加 $5$，对 $a[2]$ 单点加 $1$，对 $a[3]$ 单点加 $4$ 即可。

也有 $\mathrm{\Theta }(n)$ 的建树方法，见本页面 $\mathrm{\Theta }(n)$ 建树 一节。

复杂度分析

空间复杂度显然 $\mathrm{\Theta }(n)$。

时间复杂度：

• 对于区间查询操作：整个 $x\leftarrow x-\mathrm{lowbit}(x)$ 的迭代过程，可看做将 $x$ 二进制中的所有 $1$，从低位到高位逐渐改成 $0$ 的过程，拆分出的区间数等于 $x$ 二进制中 $1$ 的数量（即 $\mathrm{popcount}(x)$）。因此，单次查询时间复杂度是 $\mathrm{\Theta }(\log n)$；
• 对于单点修改操作：跳父亲时，访问到的高度一直严格增加，且始终有 $x\le n$。由于点 $x$ 的高度是 ${\log }_2\mathrm{lowbit}(x)$，所以跳到的高度不会超过 ${\log }_{2}n$，所以访问到的 $c$ 的数量是 $\log n$ 级别。因此，单次单点修改复杂度是 $\mathrm{\Theta }(\log n)$。

区间加区间和

前置知识：前缀和 & 差分。

该问题可以使用两个树状数组维护差分数组解决。

考虑序列 $a$ 的差分数组 $d$，其中 $d[i]=a[i]-a[i-1]$。由于差分数组的前缀和就是原数组，所以 $a_i=\sum _{j=1}^i{d}_j$。

一样地，我们考虑将查询区间和通过差分转化为查询前缀和。那么考虑查询 $a[1\dots r]$ 的和，即 $\sum _{i=1}^r{a}_i$，进行推导：

观察这个式子，不难发现每个 $d_j$ 总共被加了 $r-j+1$ 次。接着推导：

$\sum _{i=1}^r{d}_i$ 并不能推出 $\sum _{i=1}^r{d}_i\times i$ 的值，所以要用两个树状数组分别维护 $d_i$ 和 $d_i\times i$ 的和信息。

那么怎么做区间加呢？考虑给原数组 $a[l\dots r]$ 区间加 $x$ 给 $d$ 带来的影响。

因为差分是 $d[i]=a[i]-a[i-1]$，

• $a[l]$ 多了 $v$ 而 $a[l-1]$ 不变，所以 $d[l]$ 的值多了 $v$。
• $a[r+1]$ 不变而 $a[r]$ 多了 $v$，所以 $d[r+1]$ 的值少了 $v$。
• 对于不等于 $l$ 且不等于 $r+1$ 的任意 $i$，$a[i]$ 和 $a[i-1]$ 要么都没发生变化，要么都加了 $v$，$a[i]+v-(a[i-1]+v)$ 还是 $a[i]-a[i-1]$，所以其它的 $d[i]$ 均不变。

那就不难想到维护方式了：对于维护 $d_i$ 的树状数组，对 $l$ 单点加 $v$，$r+1$ 单点加 $-v$；对于维护 $d_i\times i$ 的树状数组，对 $l$ 单点加 $v\times l$，$r+1$ 单点加 $-v\times (r+1)$。

而更弱的问题，「区间加求单点值」，只需用树状数组维护一个差分数组 $d_i$。询问 $a[x]$ 的单点值，直接求 $d[1\dots x]$ 的和即可。

这里直接给出「区间加区间和」的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

int t1[MAXN], t2[MAXN], n;

int lowbit(int x) { return x & (-x); }

void add(int k, int v) {
  int v1 = k * v;
  while (k <= n) {
    t1[k] += v, t2[k] += v1;
    // 注意不能写成 t2[k] += k * v，因为 k 的值已经不是原数组的下标了
    k += lowbit(k);
  }
}

int getsum(int *t, int k) {
  int ret = 0;
  while (k) {
    ret += t[k];
    k -= lowbit(k);
  }
  return ret;
}

void add1(int l, int r, int v) {
  add(l, v), add(r + 1, -v);  // 将区间加差分为两个前缀加
}

long long getsum1(int l, int r) {
  return (r + 1ll) * getsum(t1, r) - 1ll * l * getsum(t1, l - 1) -
         (getsum(t2, r) - getsum(t2, l - 1));
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

t1 = [0] * MAXN
t2 = [0] * MAXN
n = 0


def lowbit(x):
    return x & (-x)


def add(k, v):
    v1 = k * v
    while k <= n:
        t1[k] = t1[k] + v
        t2[k] = t2[k] + v1
        k = k + lowbit(k)


def getsum(t, k):
    ret = 0
    while k:
        ret = ret + t[k]
        k = k - lowbit(k)
    return ret


def add1(l, r, v):
    add(l, v)
    add(r + 1, -v)


def getsum1(l, r):
    return (
        (r) * getsum(t1, r)
        - l * getsum(t1, l - 1)
        - (getsum(t2, r) - getsum(t2, l - 1))
    )

根据这个原理，应该可以实现「区间乘区间积」，「区间异或一个数，求区间异或值」等，只要满足维护的信息和区间操作是同种运算即可，感兴趣的读者可以自己尝试。

二维树状数组

单点修改，子矩阵查询

二维树状数组，也被称作树状数组套树状数组，用来维护二维数组上的单点修改和前缀信息问题。

与一维树状数组类似，我们用 $c(x,y)$ 表示 $a(x-\mathrm{lowbit}(x)+1,y-\mathrm{lowbit}(y)+1)\dots a(x,y)$ 的矩阵总信息，即一个以 $a(x,y)$ 为右下角，高 $\mathrm{lowbit}(x)$，宽 $\mathrm{lowbit}(y)$ 的矩阵的总信息。

对于单点修改，设：

即 $f(x,i)$ 为 $x$ 在树状数组树形态上的第 $i$ 级祖先（第 $0$ 级祖先是自己）。

则只有 $c(f(x,i),f(y,j))$ 中的元素管辖 $a(x,y)$，修改 $a(x,y)$ 时只需修改所有 $c(f(x,i),f(y,j))$，其中 $f(x,i)\le n$，$f(y,j)\le m$。

对于查询，我们设：

则合并所有 $c(g(x,i),g(y,j))$，其中 。

下面给出单点加、查询子矩阵和的代码。

1
2
3
4
5
6
7
8

void add(int x, int y, int v) {
  for (int i = x; i <= n; i += lowbit(i)) {
    for (int j = y; j <= m; j += lowbit(j)) {
      // 注意这里必须得建循环变量，不能像一维数组一样直接 while (x <= n) 了
      c[i][j] += v;
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int sum(int x, int y) {
  int res = 0;
  for (int i = x; i > 0; i -= lowbit(i)) {
    for (int j = y; j > 0; j -= lowbit(j)) {
      res += c[i][j];
    }
  }
  return res;
}

int ask(int x1, int y1, int x2, int y2) {
  // 查询子矩阵和
  return sum(x2, y2) - sum(x2, y1 - 1) - sum(x1 - 1, y2) + sum(x1 - 1, y1 - 1);
}

子矩阵加，求子矩阵和

前置知识：前缀和 & 差分 和本页面 区间加区间和 一节。

和一维树状数组的「区间加区间和」问题类似，考虑维护差分数组。

二维数组上的差分数组是这样的：

$$d(i,j)=a(i,j)-a(i-1,j)-a(i,j-1)+a(i-1,j-1)。$$

这样以来，对左上角 $(x_1,y_1)$，右下角 $(x_2,y_2)$ 的子矩阵区间加 $v$，相当于在差分数组上，对 $d(x_1,y_1)$ 和 $d(x_2+1,y_2+1)$ 分别单点加 $v$，对 $d(x_2+1,y_1)$ 和 $d(x_1,y_2+1)$ 分别单点加 $-v$。

至于原因，把这四个 $d$ 分别用定义式表示出来，分析一下每项的变化即可。

举个例子吧，初始差分数组为 $0$，给 $a(2,2)\dots a(3,4)$ 子矩阵加 $v$ 后差分数组会变为：

（其中 $a(2,2)\dots a(3,4)$ 这个子矩阵恰好是上面位于中心的 $2\times 3$ 大小的矩阵。）

因此，子矩阵加的做法是：转化为差分数组上的四个单点加操作。

现在考虑查询子矩阵和：

对于点 $(x,y)$，它的二维前缀和可以表示为：

$$\sum _{i=1}^x\sum _{j=1}^y\sum _{h=1}^i\sum _{k=1}^{j}d(h,k)$$

原因就是差分的前缀和的前缀和就是原本的前缀和。

和一维树状数组的「区间加区间和」问题类似，统计 $d(h,k)$ 的出现次数，为 $(x-h+1)\times (y-k+1)$。

然后接着推导：

所以我们需维护四个树状数组，分别维护 $d(i,j)$，$d(i,j)\times i$，$d(i,j)\times j$，$d(i,j)\times i\times j$ 的和信息。

当然了，和一维同理，如果只需要子矩阵加求单点值，维护一个差分数组然后询问前缀和就足够了。

下面给出代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

using ll = long long;
ll t1[N][N], t2[N][N], t3[N][N], t4[N][N];

void add(ll x, ll y, ll z) {
  for (int X = x; X <= n; X += lowbit(X))
    for (int Y = y; Y <= m; Y += lowbit(Y)) {
      t1[X][Y] += z;
      t2[X][Y] += z * x;  // 注意是 z * x 而不是 z * X，后面同理
      t3[X][Y] += z * y;
      t4[X][Y] += z * x * y;
    }
}

void range_add(ll xa, ll ya, ll xb, ll yb,
               ll z) {  //(xa, ya) 到 (xb, yb) 子矩阵
  add(xa, ya, z);
  add(xa, yb + 1, -z);
  add(xb + 1, ya, -z);
  add(xb + 1, yb + 1, z);
}

ll ask(ll x, ll y) {
  ll res = 0;
  for (int i = x; i; i -= lowbit(i))
    for (int j = y; j; j -= lowbit(j))
      res += (x + 1) * (y + 1) * t1[i][j] - (y + 1) * t2[i][j] -
             (x + 1) * t3[i][j] + t4[i][j];
  return res;
}

ll range_ask(ll xa, ll ya, ll xb, ll yb) {
  return ask(xb, yb) - ask(xb, ya - 1) - ask(xa - 1, yb) + ask(xa - 1, ya - 1);
}