讲义。从tops上匆匆忙忙抄过来的（格式不好没时间改请见谅

登录以参加训练计划

树状数组

引入

在之前的课程中，我们学过一种通用的维护区间查询问题的方法：倍增法。倍增法适用于所有具有 区间可加性 的区间查询问题。

什么是区间可加性？对于序列区间 $[a,b]$ ，若将其拆分为若干子区间（如 $[a,c]$ 和 $[c+1,b]$ ），若整个区间的运算结果可由子区间运算结果通过相同逻辑运算得到，则称该运算具有 区间可加性 。

比如：求区间和、区间最值、区间 GCD。（区间最值和GCD 即使区间重叠也成立）

不具有区间可加性的逻辑运算通常与 元素分布、个数的具体条件 相关，如 “数量的奇偶性”、“相邻元素关系” 等，因其结果无法通过子区间简单组合推导。

比如：求区间内是否存在相邻的 $1$ 、区间内至少有 $k(k>1)$ 个 $0$ 的个数。

倍增法的缺点也非常明显，它不能支持中间出现修改操作。例如，以一个非常简单的问题为例：

给定一个长度为 $n$ 的序列 $a$ ，进行 $q$ 次操作，操作分两种：

区间求和，给定 $l, r$ ，查询 $a_l + a_{l + 1} + \dots + a_r$ 的答案。

单点修改，给定 $x, k$ ，将 $a_x$ 加上 $k$ （或者 $a_x$ 修改为 $k$ ，这个是等价的，只需要你记录一下当前 $a$ 序列的取值，就可以互相转换）。

$n \leq 10^5$ ， $q\leq 10^5$

这个问题采用倍增法是无法解决的，因为如果我们进行单点修改，受影响的倍增的预处理信息多达 $O(n)$ 个。

能不能用一维前缀和解决呢？维护一个数组的前缀和 $sum[i]= a[1]+a[2]+...+a[i]$ ，但是不难发现，如果我们修改了任意一个 $a[i]$ ， $sum[i],sum[i+1],...,sum[n]$ 都会发生变化。可以说，每次修改 $sum[i]$ 后，调整前缀和 $sum$ 也需要 $O(n)$ 的时间。一样无法处理。

这时候，我们可以使用一个“前缀和的升级版”的数据结构：树状数组。

什么是树状数组

树状数组通过二进制拆分的思想（类似于树上倍增），将前缀和 $sum[n]=\sum_{i=1}^{n} a[i]$ 拆分成 $popcount(n)$ 个区间和，进而可以在 $O(\log n)$ 的时间复杂度内求出任意一个区间和，如果修改某一个元素的值，那么也可以做到 $O(\log n)$ 时间复杂度更新受影响的区间和，这使得两种操作都不会太慢。

数据结构	快速求前缀和（区间求和）	修改某一个数（单点修改）
树状数组	$O(\log n)$
数组	$O(n)$	$O(1)$
前缀和数组	$O(1)$	$O(n)$
差分数组	$O(n)$	$O(1)$

如果一个问题，同时具有区间可加性和可减性，并且是带有修改的，那么就可以用树状数组来维护。

什么是可减性呢？考虑一个区间 $[l, r]$ ，如果 $[l, r]$ 上的答案等于 $[1, r]$ 上的答案减去 $[1, l - 1]$ 上的答案，那么就满足可减性。

比如，上面的问题，求一个区间所有元素的和，当然具有可减性。接下来，我们将介绍树状数组的结构，以及解答为什么它能解决带有修改操作的问题。

树状数组的结构

一维前缀和回顾

我们先来回顾一下一维前缀和的思想。当我们要求某个区间 $[l,r]$ 上的元素和时，我们提前预处理出了 $sum[i] = a[1]+a[2]+...+ a[i]$ 的和，即

$$ sum[i] = \sum_{k=1}^{i} a[k] $$

对于区间 $[l,r]$ 上的元素和，我们用 $sum[r]$ 和 $sum[l-1]$ 就可以直接表示出来：

$$ \sum_{i=l}^{r} a[i] = sum[r] - sum[l-1] $$

如果没有单点修改操作，那这个数组就太完美了。但是，有了单点修改操作之后，修改会影响 $O(n)$ 个前缀和数组的值。能不能让这个影响减少一点呢？

树状数组和前缀和的关系

树状数组是这么降低影响的——修改 $sum[i]$ 的定义为以 $i$ 作为右端点，长度（元素个数）为 $\texttt{lowbit}(i)$ 个的区间的元素和。为了和前缀和区分开来，我们将这么定义得到的“前缀和数组”记作 $c[]$ 数组，即

$$ c[i] = \sum_{k=i-lowbit(i)+1}^{i} a[k] $$

还记得什么是 $\texttt{lowbit}(i)$ 吗？它表示数字 $i$ 在二进制下只保留最低位的 $1$ 所得到的数字，它一定是一个 $2$ 的非负整数次幂。比如：

$x$	1	2	3	4	5	6	7	8	9	10	11	12	13	14
$\texttt{lowbit}(x)$	1	2	1	4	1	2	1	8	1	2	1	4	1	2

那么为什么这么定义 $c[]$ 数组呢？这是因为我们可以反复利用 lowbit() 操作，将任何数字拆分成 $O(\log n)$ 个 $2$ 的非负整数次幂的和（二进制下的各个 $1$ ），比如：

$10=(1010)_2=8+2$
$15=(1111)_2=8+4+2+1$
$108=(1101100)_2=64+32+8+4$
$1024=(10000000000)_2=1024$

树状数组的区间查询

既然任何数字都可以拆成若干个 $2$ 的非负整数次幂，那么任何长度的前缀和是不是也可以拆成若干个子区间的和呢？

答案是可以的，以上面数字为例：

$sum[10] = (a[1]+a[2] +...+ a[8])+(a[9]+a[10])$
$sum[15] = (a[1]+a[2] +...+ a[8])+(a[9]+a[10]+a[11]+a[12])+(a[13]+a[14])+(a[15])$
$sum[108]=(a[1]+a[2]+...+a[64])+(a[65]+...+a[96])+(a[97]+...+a[104])+(a[105]+...+a[108])$
$sum[1024] = (a[1]+a[2]+...+a[1024])$

根据 $c[]$ 数组的定义，上面这些等式可以表示为：

$sum[10] = c[8] + c[10] = c[10-\texttt{lowbit}(10)]+c[10]$
$sum[15] = c[8]+c[12]+c[14]+c[15]$
$sum[108] = c[64]+c[96]+c[104]+c[108]$
$sum[1024] = c[1024]$

可以看出，如果记 $sum[i] = c[x_1]+c[x_2]+...+c[x_k]$ 的话，且假设 $x_1\lt x_2\lt ...\lt x_k$ ，那么必然有

$x_k=i$
$k=popcount(i)$
$x_{j-1}=x_j-\texttt{lowbit}(j)$ ， $1\lt j\le k$

注意到 popcount(n) 的结果是 $O(\log n)$ 的，这也意味着 一个前缀和可以拆分成 $O(\log n)$ 个上面的区间和 。所以，对于一开始的 区间求和+单点修改问题 ，我们可以 把区间求和转化为求两个前缀和，再把两个求前缀和转化为求 $O(\log n)$ 个区间的和 。

事实上，如果对于每个 $c[x]$ ，将其连向大于 $x$ 且 能覆盖 $x$ 所对应区间的最小的数字 （把它看作 父结点 ）。那么数组 $c[]$ 可以构成一个如下图所示的 树形结构 （严格来说是森林），这也是树状数组这个名称的由来。

代码实现如下：

int lowbit(int x) {
  return x&-x;
}
int sum(int x) {  // 求前缀和 sum[x]
  int res = 0;
  while(x) {
    res += c[x];
    x -= lowbit(x);
  }
  return res;
}
int query(int l, int r) {  // 区间求和 a[l]~a[r]
  return sum(r) - sum(l-1);
}

树状数组的单点修改

现在，我们再来考虑单点修改操作，当我们修改某个元素 $a[x]$ 时，只有覆盖了 $a[x]$ 的区间和元素 $c[?]$ 会受到影响。

那么哪些区间会受影响呢？首先，最小的区间就是 $c[x]$ ，然后，由于区间的覆盖关系被我们转化成了树上的父子关系，因此，后序我们只要不断往上更新父结点的区间和，直至到根结点即可。

观察上面的树形结构可以发现，结点 $x$ 的父结点是 $x+\texttt{lowbit}(x)$ ，于是，我们可以得到下面的单点修改代码：

void add(int x, int k) {  // 单点修改 a[x] += k
  while(x <= n) {
    c[x] += k;
    x += lowbit(x);
  }
}

问：为什么 $c[x]$ 的父结点是 $c[x+\texttt{lowbit}(x)]$ ?

答：假设 $x$ 的父结点是 $x+y$ ，根据 $c[]$ 数组的定义， $c[x]$ 对应的区间为 $[x-\texttt{lowbit}(x)+1, x]$ ，其父结点对应的区间应包含区间 $[x-\texttt{lowbit}(x)+1, x]$ ，且根据定义，其区间为 $[x+y-\texttt{lowbit}(x+y)+1, x+y]$ 。我们可以证明 $y=\texttt{lowbit}(x)$ 满足该条件且最小——

（1）证明 $y=\texttt{lowbit}(x)$ 可以覆盖 $x$ 所在区间。

从二进制角度考虑，假设 $x$ 末尾有 $k$ 个 $0$ ，那么 $y=\texttt{lowbit}(x)=2^{k}$ ， $x$ 对应的区间为 $[x-2^{k}+1, x]$ 。

因为 $y=x+\texttt{lowbit}(x)$ ，所以在二进制下， $x+y$ 末尾至少有 $k+1$ 个 $0$ ，这也意味着 $x+y$ 对应区间的长度 $\ge 2^{k+1}$ ，对应区间的左端点最大为 $x+y-2^{k+1}+1=x-2^{k}+1$ 。

又因为 $c[x+y]$ 的区间右端点大于 $x$ ，所以 $x+y$ 对应的区间范围包含 $x$ 的区间。

（2）证明 $y=\texttt{lowbit}(x)$ 是最小的。

从二进制角度考虑，如果 $y \lt \texttt{lowbit}(x)$ 则 $\texttt{lowbit}(x+y)$ 必然小于 $\texttt{lowbit}(x)$ ，其区间必然无法覆盖 $x$ 对应的区间。

综上，得证。

树状数组的初始化

现在，我们学会了如何在树状数组上进行区间查询以及单点修改操作。但是，如何由一个序列得到对应的树状数组呢？

其实我们无需额外去做初始化工作，只需将序列认为初始时全部为 $0$ ，把输入得到元素 $a_i$ 的过程看作将第 $i$ 个元素增加 $a_i$ 即可。这个初始化的时间复杂度是 $O(n\log n)$ 的。

代码实现如下：

cin >> n;
for(int i = 1; i <= n; i++) {
  cin >> a[i];
  add(i, a[i]);
}

注意事项： 树状数组的下标不能从 $0$ 开始使用，因为 $\texttt{lowbit}(0)=0$ ，进行查询时会陷入死循环。

如果我们追求更高的初始化效率，也可以采用以下两种 $O(n)$ 的做法：

前面我们知道 $c[i]$ 表示的是区间 $[i-\texttt{lowbit}(i)+1, i]$ 上的和，所以可以先预处理出前缀和数组 $sum[]$ ，再计算 $c[]$ 数组。如此，可以 $O(n)$ 建树，不过空间常数会增加。
每一个结点的值是由所有与自己直接相连的儿子的值求和得到的，因此可以倒着考虑贡献，即每次确定完儿子的值后，用儿子的值更新直接父亲的值。

参考代码如下：

// 利用前缀和建树
void init() {
  for (int i = 1; i <= n; ++i) {
    t[i] = sum[i] - sum[i - lowbit(i)];
  }
}
// 倒序（自下而上）更新树
void init() {
  for (int i = 1; i <= n; ++i) {
    c[i] += a[i];
    int j = i + lowbit(i);
    if (j <= n) c[j] += c[i];
  }
}

树状数组与差分

思考一个和上面类似的问题—— 区间修改，单点查询 ：

给定一个长度为 $n$ 的序列 $a$ ，进行 $q$ 次操作，操作分两种：

区间修改，给定 $l, r,k$ ，将 $a_l, a_{l + 1}, \dots, a_r$ 的值都增加 $k$ 。

单点查询，给定 $x$ ，将 $a_x$ 加上 $k$ （或者 $a_x$ 修改为 $k$ ，这个是等价的，只需要你记录一下当前 $a$ 序列的取值，就可以互相转换）。

这个问题该怎么处理呢？如果用上面的树状数组，就必须把 $l\sim r$ 区间内每个值都更新，这样的时间复杂度肯定是不行的。

我们已经知道，区间 $[l,r]$ 加 $k$ 操作转化到差分数组 $d$ 上就变成两次单点修改操作： $d[l]+=k$ 和 $d[r+1]-=c$ 操作。而单点查询 $a[x]$ 的操作，根据差分数组的定义， $a[x] = \sum_{i=1}^x d[i]$ 。

发现了吗？现在， 区间修改操作变成了差分数组上的两次单点修改操作。单点查询操作，变成了差分数组上的一次前缀求和操作 。

这个转换太美妙了！问题被完美地转化成了可以用树状数组高效处理的“单点修改”和“前缀和查询”。我们只需要用一个树状数组来维护差分数组 $d[]$ 即可。时间复杂度同 单点修改+区间查询 。

基本代码如下：

cin >> n;
for(int i = 1; i <= n; i++) {
  cin >> a[i];
  add(i, a[i]-a[i-1]);  // 用差分构建树状数组
}
// 区间修改操作
cin >> l >> r >> k;
add(l, k); add(r+1, -k);   // 两次单点修改操作
// 单点查询
cin >> x;
cout << sum(x) << '\n';

区间修改+区间查询

这是前缀和与差分思想应用的顶峰之一。问题升级为： 要求支持序列的区间修改 +。区间查询 。

我们已经知道如何用一个树状数组维护差分数组 $d[]$ 来实现区间修改。现在的问题是，如何计算区间 $[l,r]$ 的和，即 $\sum_{i=l}^r a[i]$ ？

这等价于计算 $\sum_{i=1}^r a[i] - \sum_{i=1}^{l-1} a[i]$ ，又因为 $a[k] = \sum_{i=1}^k d[i]$ ，那么， $a[]$ 的前缀和就是

$$ \sum_{k=1}^x a[k] = \sum_{k=1}^x\sum_{i=1}^k d[i] $$

这个双重求和的式子直接计算起来很麻烦。我们需要对它进行变形。考虑每个 $d[i]$ 对总和的贡献。 $d[i]$ 会在 $a[i]\sim a[x]$ 中出现，共出现了 $x-i+1$ 次。因此，上式可以改写为：

$$ \begin {aligned} \sum_{k=1}^x a[k] &= \sum_{i=1}^x (x-i+1)\cdot d[i]\\ &=\sum_{i=1}^x (x+1)\cdot d[i] - \sum_{i=1}^x i\cdot d[i]\\ &=(x+1)\sum_{i=1}^x d[i] - \sum_{i=1}^x i\cdot d[i] \end {aligned} $$

观察这个最终的公式。它把 $a[]$ 的前缀和查询，转化为了两个部分的差：

$\sum_{i=1}^x d[i]$ ：这是差分数组 $d[]$ 的前缀和。
$\sum_{i=1}^x (i\cdot d[i])$ ：这是一个新数组 $d'[]$ 的前缀和，其中 $d'[i]=i\cdot d[i]$ 。

这两个部分都是标准的前缀和查询形式！我们可以用 两个树状数组 来分别维护它们：

第一个树状数组 $c1[]$ 维护 $d[i]$ 。
第二个树状数组 $c2[]$ 维护 $i*d[i]$ 。

当进行区间 $[l,r]$ 加 $k$ 操作时：

$d[l]+=k,d[r+1]-=k$ 。
对应到 $c1[]$ 上，是 $add(c1, l, k)$ 和 $add(c2, r+1, -k)$ 。
对应到 $c2[]$ 上，是 $add(c2, l, l*k)$ 和 $add(c2, r+1, -(r+1)*k)$ 。

当查询前缀和 $\sum_{k=1}^x a[k]$ 时：

$sum1 = query(c1, x)$
$sum2 = query(c2, x)$
前缀和为 $(x+1)*sum1 - sum2$ 。

有了查询前缀和的方法，查询区间和的方法就自然有了。

这个技巧将差分思想的威力发挥到了极致，它告诉我们，通过巧妙的 数学变形 ，看似复杂的操作可以被分解为若干个基础操作的组合（ 化繁为简 ）。

参考代码如下：

long long c1[N];   // 维护 (d[1] + d[2] + ... + d[n])
long long c2[N];   // 维护 (1*d[1] + 2*d[2] + ... + n*d[n])
// 差分数组上的单点修改
void add(int x, int k) {
    long long k1 = x*k;  // 注意不能在下面循环内写成 c2[x] += x*k，因为 x 在变化
    while(x <= n) {
        c1[x] += k;
        c2[x] += k1;
        x += lowbit(x);
    }
}
// 差分数组上的前缀求和
long long sum(int x) {
    long long res = 0, xx = x;
    while(x) {
        res += (xx+1)*c1[x] - c2[x];
        x -= lowbit(x);
    }
    return res;
}
// 构建操作
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
add(i, a[i]-a[i-1]);
}
// 区间修改操作 a[l]~a[r] += x
cin >> l >> r >> x;
add(l, x);
add(r+1, -x);
// 区间查询操作
cin >> l >> r;
cout << sum(r) - sum(l-1) << '\n';

</p>

算法竞赛的很多难题，其突破口就在于找到一个合适的变换，将一个棘手的问题，映射到一个我们拥有成熟解决方案的经典模型上。前缀和与差分，正是这种变换思想最朴素、最直接的体现。

树状数组与逆序对

先来回顾一道我们做过的题目：

逆序对（二维偏序）：对于一个序列 $a[]$ ，如果有 $i\lt j$ 且 $a[i] > a[j]$ ，则称 $a[i],a[j]$ 构成一个逆序对。现有一个长度为 $n$ 的数组 $a[]$ ，求其上的逆序对的个数。（排列的逆序对个数是它恢复成正序序列所需要做相邻对换的最少次数）

$n\le 2\times 10^5$ ， $|a_i|\le 10^9$ 。

这个问题，我们已经会用归并排序解决了。现在，我们来用树状数组解决。任意给定一个集合 $a$ ，如果用 $t[val]$ 保存数值 $val$ 在集合 $a$ 中出现的次数，那么数组 $t$ 在 $[l,r]$ 上的区间和（即 $\sum_{i=1}^{r}t[i]$ ）就表示集合 $a$ 中范围在 $[l,r]$ 内的数有多少个。

我们可以在集合 $a$ 的数值范围上建立一个树状数组，来维护 $t$ 的前缀和。这样即使在集合 $a$ 中插入或删除一个数，也可以高效地进行统计：

在序列 $a$ 的数值范围上建立树状数组，初始化为全零。
倒序扫描给定的序列 $a$ ，对于每个数 $a[i]$ ：
(1) 在树状数组中查询前缀和 $[1,a[i]-1]$ ，累加到答案 $ans$ 中。
(2) 执行“单点增加”操作，即把位置 $a[i]$ 上的数加 $1$ (相当于 $t[a[i]]++$ )，同时正确维护 $t$ 的前缀和。这表示数值 $a[t]$ 又出现了 $1$ 次。
$ans$ 即为所求逆序对个数。

在这个算法中，因为倒序扫描，“已经出现过的数”就是在 $a[i]$ 后边的数，所以我们通过树状数组查询的内容就是“每个 $a[i]$ 后边有多少个比它小”。每次查询的结果之和当然就是逆序对个数。时间复杂度为 $O((N + M) \log M)$ ， $M$ 为数值范围的大小。

当数值范围较大时，当然可以先进行离散化，再用树状数组进行计算。不过因为离散化本身就要通过排序来实现，所以在这种情况下就不如直接用归并排序来计算逆序对数了。

参考代码如下：

int n, t, b[N], c[N], cnt;
long long ans;
pair<int, int> a[N];
// ... 树状数组实现
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i].first;
		a[i].second = i;
	}
	sort(a+1, a+n+1);
	// b[i]: 原数组元素 a[i] 是原数组去重离散化后第 b[i] 大的数字
	cnt = 1;  b[a[1].second] = cnt;
	for(int i = 2; i <= n; i++) {
	    if(a[i].first != a[i-1].first)  cnt++;
	    b[a[i].second] = cnt;
	}
	for(int i = n; i; i--) {  // 倒序扫描
	    ans += sum(b[i]-1); // 比 a[i] 小的数字的数量
	    add(b[i], 1);
	}
	cout << ans;
}

高维树状数组

在一维树状数组中， $c[x]$ （树状数组中的那个“数组”）记录的是右端点为 $x$ 、长度为 $\texttt{lowbit}(x)$ 的区间的区间和。

那么在二维树状数组中，可以类似地定义 $c[x][y]$ 记录的是右下角为 $(x, y)$ ，高为 $\texttt{lowbit}(x)$ , 宽为 $\texttt{lowbit}(y)$ 的区间的区间和。

时间复杂度上，一维的树状数组的每个操作的复杂度都是 $O(\log n)$ 的，非常高效。它可以扩充为 $D$ 维，这样每一个操作的复杂度就变成了 $O(\log^D n)$ ，在 $D$ 不大的时候，时间复杂度是可以接受的。

实现起来，扩充的方法可以是将原来的修改和査询函数中的一个循环，改成 $D$ 层循环修改和查询 $D$ 维的树状数组 $c$ 中的操作。

以二维树状数组维护二维数组上的 单点修改+区间查询 为例：

// 单点修改操作 a[x][y] += k
void add(int x, int y, int k) {
  for (int i = x; i <= n; i += lowbit(i)) {
    for (int j = y; j <= m; j += lowbit(j)) {
      c[i][j] += k;
    }
  }
}
// 查询二维前缀和 sum[x][y]
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);
}

</p>

区间修改+单点查询

我们对于一维数组进行差分，是为了使差分数组前缀和等于原数组对应位置的元素。

那么如何对二维数组进行差分呢？可以针对二维前缀和的求法来设计方案。二维前缀和：

$$ sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j] $$

那么我们可以令 $sum$ 表示原数组， $a$ 表示差分数组，于是有：

$$ a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + d[i][j] $$

移项就得到二维差分数组的计算公式来：

$$ d[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1] $$

例如下面这个矩阵

 1  4  8
 6  7  2
 3  9  5

对应的差分数组就是

 1  3  4
 5 -2 -9
-3  5  1

当我们想要将一个矩阵加上 $x$ 时，怎么做呢？下面是给最中间的 $3\times 3$ 矩阵加上 $x$ 时，差分数组的变化：

0  0  0  0  0
0 +x  0  0 -x
0  0  0  0  0
0  0  0  0  0
0 -x  0  0 +x

这样修改差分，对原数组造成的影响就是：

0  0  0  0  0
0  x  x  x  0
0  x  x  x  0
0  x  x  x  0
0  0  0  0  0

所以，如果我们要将区间 $(a,b)\sim(c,d)$ 上的元素都增加 $k$ ，那么在二维差分数组上，我们需要修改四个点：

$$ add(a,b, k)\\add(a,d+1,-k)\\add(c+1,b,-k)\\add(c+1,d+1,k) $$

查询单点就是简单的： $sum(c,d)$

区间修改+区间查询

类比之前一维数组的区间修改区间查询，下面这个式子表示的是点 $(x, y)$ 的二维前缀和：

$$ \sum_{i=1}^x\sum_{j=1}^y\sum_{k=1}^i\sum_{h=1}^jd[h][k] $$

$d[h][k]$ 为点 $(h,k)$ 对应的“二维差分”(同上)，这个式子非常复杂( $O(n^4)$ 复杂度！但利用树状数组，我们可以把它优化到 $O(\log^2 n)$ 。

首先，类比一维树状数组，统计一下每个 $d[h][k]$ 出现过多少次：

$d[1][1]$ 出现了 $x\times y$ 次。
$d[1][2]$ 出现了 $x\times (y−1)$ 次。
......
$d[h][k]$ 出现了 $(x−h+1)\times (y−k+1)$ 次。

那么这个式子就可以写成：

$$ \sum_{i=1}^x\sum_{j=1}^y d[i][j]\times (x+1−i)\times (y+1−j) $$

把这个式子展开，就得到：

$$ (x + 1) \times (y + 1) \times \sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j]\\ − (y + 1) \times \sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j] \times i\\ − (x + 1) \times \sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j] \times j\\ + \sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j] \times i \times j $$

那么我们要开四个树状数组，分别维护：

$$ \begin {aligned} &d[i][j]\\ &d[i][j]\times i\\ &d[i][j]\times j\\ &d[i][j]\times i\times j \end {aligned} $$

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

单次修改或者查询的时间复杂度均是 $O(\log^2 n)$ 的。下面给出代码：

long long tr1[N][N], tr2[N][N], tr3[N][N], tr4[N][N];
void add(int x, int y, int k){
  int rx = x, ry = y;
	for(int i = x; i <= n; i+=lowbit(i)) {
		for(int j = y; j <= m; j+=lowbit(j)) {
      tr1[i][j] += k;
      tr2[i][j] += rx*k;
      tr3[i][j] += ry*k;
      tr4[i][j] += rx*ry*k;
		}
	}
}
// (a,b) 到 (c,d) 子矩阵区间加 k
void range_add(int a, int b, int c, int d, int k) {
  add(a, b, k);
  add(a, d+1, -k);
  add(c+1, b, -k);
  add(c+1, d+1, k);
}
long long sum(int x, int y) {
long long res = 0;
int rx = x+1, ry = y+1;
for (int i = x; i > 0; i -= lowbit(i)) {
for (int j = y; j > 0; j -= lowbit(j)) {
res += rxrytr1[i][j]-rytr2[i][j]-rxtr3[i][j]+tr4[i][j];
}
}
return res;
}
// (a,b) 到 (c,d) 子矩阵区间求和
long long range_query(int a, int b, int c, int d) {
return sum(c,d)-sum(c,b-1)-sum(a-1,d)+sum(a-1,b-1);
}

</p>

练习

例 4

P4100 谜一样的牛：有 $n$ 头奶牛，已知它们的身高为 $1 \sim n$ 且各不相同，但不知道每头奶牛的具体身高。

现在这 $n$ 头奶牛站成一列，已知第 $i$ 头牛前面有 $a_i$ 头牛比它低，求每头奶牛的身高。

$n \leq 10^5$

如果我们从后往前看，对于最后一头牛，如果说前面有 $a_n$ 头牛比它低，那我们就能唯一确定，它是一头高度为 $a_n + 1$ 的牛，这是因为总共 $n$ 头牛一定涵盖了 $1 \sim n$ 的所有身高。

既然我们知道了最后一头牛的身高，那我们把这个身高给扣除，此时，我就可以根据倒数第二头牛所报的数字，推断倒数第二头牛的身高。

具体的，我们可以构建一个树状数组，用来维护一个 01 序列，这个 01 序列的第 $i$ 位用来表示身高 $i$ 已经被身后的牛给使用过了。那么接下来，假设此时已经访问到了第 $j$ 头牛，我们只需要找到这个 01 序列上到底哪个位置，会使得它前面 0 的个数正好等于 $a_j$ ，我们就知道它的身高是多少了。所以我们可以采用二分法，二分一个位置，然后用树状数组，数出来前面 0 有多少个（其实就是数前面 1 有多少个），就知道这个身高是小了还是大了。

时间复杂度为 $O(n \log^2 n)$ 。

例 5

P4092 数星星 Stars：按顺序输入 $n$ 个二维平面内的点 $(x,y)$ ，保证坐标按 $y$ 增序给出， $y$ 相同时按 $x$ 增序给出。定义每个星星的星级为其左下方（包含正左和正下）的星星的数量。统计出每个星级的星星的数量。

$n\le 15000$ ， $0\le x,y\le 32000$

因为输入的数据保证先按 $y$ 递增输入， $y$ 相同再按 $x$ 递增输入，所以，直接开一个一维的树状数组统计每个横坐标处已经有的星星的个数即可，无需使用二维树状数组处理。

这是一个单点修改 + 区间查询问题。

例 6

P4093 校门外的树：校门外有条长度为 $n$ 的道路总，路旁很多树，学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有 $m$ 个操作，操作有两种：

$k=1$ ，读入 $l,r$ 表示在 $l$ 到 $r$ 之间种上一种树，每次操作种的树的种类都不同；

$k=2$ ，读入 $l,r$ 表示询问 $l$ 到 $r$ 之间有多少种树。

注意：每个位置都可以重复种树。

$1\le n,m\le 5\times 10^4$ ，保证 $1\le l,r\le n$

如果你尝试在草稿纸上画一下，就会发现，这里的种上一种树操作就是增加一个区间，询问操作就是问 $[l,r]$ 上出现过多少个区间。

让我们来借用一下前缀和和差分的思想： 将对区间的处理转化为对应左右端点的处理 。类似于 P3575 区间分组，我们将区间的左右端点做不同的处理。

让我们来想像一下， $n$ 个区间排列在平面上，有一条（扫描）线从左往右匀速扫过去。当扫描线碰到一个左端点时，就意味着出现了一个新的区间（但区间的长度还不确定），当扫描线碰到并越过一个右端点时，就意味着出现了一个完整的区间，并且区间已经和扫描线分离。如果我们关心经过扫描线的区间个数，那么只需统计从扫描开始到现在经过的右端点个数 $right$ 和左端点个数 $left$ ，区间个数即为 $right-left$ 。

由于我们关心的是区间 $[l,r]$ 上出现过多少个区间。所以，我们可以放两条扫描线，一条从开始 $0$ 处扫到 $r$ ，一条扫到 $l$ 。那么，区间 $[l,r]$ 上的区间数量就是 $[1,r]$ 上出现的区间数量减去 $[1,l-1]$ 上的完整区间的数量，即 $left_r-right_{l-1}$ 。

所以，我们可以分别开两个树状数组，维护 $[1,n]$ 上每个位置左端点的个数和右端点的个数即可。

例 7

P1161 火柴排队：Topscoding1161 火柴排队：你有两个长度都为 $n$ 的序列 $a, b$ ，定义这两个序列之间的距离为 $\sum_{i = 1}^{n}(a_i - b_i)^2$ ，你可以交换 $a$ 或者 $b$ 中相邻的数字，你希望通过尽量少的交换次数，使得两个序列之间的距离最小。问需要最少交换几次。

$n \leq 10^5$ ， $0 \leq a_i, b_i \leq 2^{31} - 1$

这里给大家提供一个 经验：凡是带有平方的式子，一般情况下都需要你拆开 。例如 HNOI/AHOI 2017 的礼物，HNOI2008 的玩具装箱，都是需要拆开带有平方的式子的。我们把平方项给拆开，那么距离就可以表示成

$$ \begin {aligned} \sum_{i = 1}^{n}(a_i - b_i)^2 &=\sum_{i = 1}^{n}(a_i^2 + b_i^2 - 2a_ib_i) \\ &= \sum_{i = 1}^{n}a_i^2 + \sum_{i = 1}^{n}b_i^2 - 2\sum_{i = 1}^{n}a_ib_i \end {aligned} $$

可以发现，距离的前两项是定值，不会影响到距离的。能影响距离大小的只有最后一项 $\sum_{i = 1}^{n}a_ib_i$ 。

在高中学习不等式（新课标普通高中课程标准试验教科书人教版选修4-5第三讲第三节）的时候，我们会学到排序不等式，排序不等式讲的是非常符合直觉的一件事情： 顺序和 $\geq$ 乱序和 $\geq$ 逆序和 。就是说：

给你两个长度相等的序列，将他们都按升序排好序，那么他们对应项乘起来再相加是最大的（顺序和，逆序对数量最少）；
如果一个按升序，一个按降序，那么对应项乘起来再相加就是最小的（逆序和，逆序对数量最多）。
乱序时的和则是介于两者中间。

我们希望这个值最大，所以是希望 $a,b$ 数组小的对应小的，大的对应大的（就如田忌赛马中齐王的获胜方式一样），然后就是求交换到这样状态时的交换次数。

我们可以令 $a$ 不动，只让 $b$ 动。由于我们可以知道每个 $a$ 的相对大小（也就是它是第几大的），所以它需要的 $b$ 是哪一个我们自然也知道，我们可以给每个 $b$ 标记上它需要走到第几个位置上去，这样，我们就是对 $b$ 求逆序对了。对于相同大小的 $a_i$ ，他们对应的每个 $b$ 的取值是一个区间，我们需要给对应的 $a$ 和对应的 $b$ 按顺序一一对应，这样才是交换次数最小的。

什么是排序不等式

设 $x_1 \leq x_2 \leq \cdots \leq x_n$ 和 $y_1 \leq y_2 \leq \cdots \leq y_n$ 是两组实数， $z_1,z_2,z_3,...,z_n$ 是 $\{y\}$ 的乱序排列，那么排序不等式表明：

$$ \sum_{i = 1}^{n} x_i y_{n - i + 1} \leq \sum_{i = 1}^{n} x_i z_i \leq \sum_{i = 1}^{n} x_i y_i $$

即 顺序和大于等于乱序和，乱序和大于等于逆序和 。特别地，如果 $\{x\}$ 和 $\{y\}$ 都严格递增，则 $\leq$ 可以改为 $\lt $ 。

证明排序不等式：

先证明顺序和最大。假设存在某个 $\{y\}$ 的乱序排列 $\{z\}$ ，使得 $\sum_{i = 1}^{n} x_i z_i > \sum_{i = 1}^{n} x_i y_i$ 。由于 $\{z\}$ 不是恒等排列，所以存在某个逆序对 $(i, j)$ 使得 $i \lt j \wedge z_i>z_j$ 。

交换 $z_i$ 和 $z_j$ ，此时乘积和的变化为：

$$ \begin {aligned} \Delta &= (x_iz_j+x_jz_i)-(x_iz_i+x_jz_j) \\ &=(x_i-x_j)(z_i-z_j) \end {aligned} $$

由于 $x_i \leq x_j$ 且 $z_i\ge z_j$ ，所以 $\Delta \geq 0$ 。这说明，减少一个逆序对（调整 $z_i,z_j$ 的顺序）之后，乘积和变大了。如此，我们可以不断减少逆序对，使得乘积和不断变大。

所以，当逆序对全部消失时，乘积和最大，即序列全部顺序时，乘积和最大。

用同样的方法，可以证明逆序和最小。

得证。

总结：对于类似的排列问题，可以用同样的调整法证明。

展开收缩

题目	尝试	AC	难度
1 A+B	166	87	入门

参加人数: 0
创建人: zap2727

树状数组

引入

什么是树状数组

树状数组的结构

一维前缀和回顾

树状数组和前缀和的关系

树状数组的区间查询

树状数组的单点修改

树状数组的初始化

树状数组与差分

区间修改+区间查询

树状数组与逆序对

高维树状数组

区间修改+单点查询

区间修改+区间查询

练习

章节 1. 无需做题

开放

状态

开发

支持

关于

数据结构	快速求前缀和（区间求和）	修改某一个数（单点修改）
树状数组	\(O(\log n)\)
数组	\(O(n)\)	\(O(1)\)
前缀和数组	\(O(1)\)	\(O(n)\)
差分数组	\(O(n)\)	\(O(1)\)

树状数组

引入

什么是树状数组

树状数组的结构

一维前缀和回顾

树状数组和前缀和的关系

树状数组的区间查询

树状数组的单点修改

树状数组的初始化

树状数组与差分

区间修改+区间查询

树状数组与逆序对

高维树状数组

区间修改+单点查询

区间修改+区间查询

练习

章节 1. 无需做题

开放

状态

开发

支持

关于

还没有账户？

登录