树状数组基础

树状数组，是一种可以在 $O(\log n)$ 的时间内，实现单点修改和查询前缀和的操作数据结构。

如何实现呢？我们先从查询前缀和开始。

若一个正整数 $x$ 的二进制形式可以被表示为 $b_{k - 1}b_{k - 2}\dots b_1b_0$ ，其中等于 $1$ 的位有 $\{b_{i_1}, b_{i_2}, \cdots, b_{i_m}\}$ ， $x$ 可以被分解为 $2^{i_1} + 2^{i_2} + \cdots + 2^{i_m}$ 的形式。

然后，查询一个前缀和就相当于查询区间 $[1, x]$ 的和。

设 $i_1 > i_2 > \cdots > i_m$ ，则区间 $[1, x]$ 可以被划分为 $m$ 个不重叠的区间：

$[1, 2^{i_1}]$ ，

$[2^{i_1} + 1, 2^{i_1} + 2^{i_2}]$ ，

$[2^{i_1} + 2^{i_2} + 1, 2^{i_1} + 2^{i_2} + 2^{i_3}]$ ，

$\cdots$ ，

$[2^{i_1} + 2^{i_2} + \cdots + 2^{i_{m - 1}} + 1, x]$ 。

（ $x = 2^{i_1} + 2^{i_2} + \cdots + 2^{i_m}$ ）

这些区间的长度分别为 $2^{i_1}, 2^{i_2}, \cdots, 2^{i_m}$ 。

设第 $i$ 个区间的结尾为 $r_i$ ，则第 $i$ 个区间的长度为 $\operatorname{lowbit}(r_i)$ 。

树状数组就使用了这种思想。具体来讲，对于一个需要维护的序列 $a$ ，建一个序列 $s$ ， $s_i$ 的值为 $\sum_{j = i - \operatorname{lowbit}(i)}^i a_i$ 。

假如我们要查询 $[1, 7]$ 的前缀和。

$[1, 7]$ 可以被划分为 $3$ 个区间： $[1, 4], [5, 6], [7, 7]$ 。

如图，我们首先从 $s_7$ 开始， $s_7 = [7, 7]$ ，把结果加上 $s_7$ 。

我们从 $s_7$ 往前跳 $\operatorname{lowbit}(7) = 1$ 步，跳到 $s_6$ ， $s_6 = [5, 6]$ ，把结果加上 $s_6$ 。

我们从 $s_6$ 往前跳 $\operatorname{lowbit}(6) = 2$ 步，跳到 $s_4$ ， $s_4 = [1, 4]$ ，把结果加上 $s_4$ 。

我们从 $s_4$ 往前跳 $\operatorname{lowbit}(4) = 4$ 步，跳到 $s_0$ ，发现 $0$ 已经不被 $[1, 7]$ 包含，返回结果。

可以写出查询前缀和的代码：

int query(int p){
	int sum = 0;
	while (p) sum += s[p], p -= lowbit(x);
	return sum;
}

单点增加，就是修改 $a_x$ ，并正确维护 $s$ 数组。显然，我们只需要将 $s$ 数组内包含 $a_x$ 的项增加。

可以写出单点修改的代码：

void update(int p, int x){
	while (p <= n) s[p] += x, p += lowbit(p);
}

模板题一代码（查询 $[l, r]$ 时只需查询 $[1, r] - [1, l - 1]$ 即可）：

#include <algorithm>
#include <cstdio>

using namespace std;

int n, m, t[500001], tt, ttt, tttt;
int lowbit(int x){
	return x & -x;
}
void add(int i, int x){
	while (i <= n){
		t[i] += x;
		i += lowbit(i);
	}
}
int sum(int i){
	int s = 0;
	while (i > 0){
		s += t[i];
		i -= lowbit(i);
	}
	return s;
}
int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1;i <= n;i ++) scanf("%d", &tt), add(i, tt);
	for (int i = 1;i <= m;i ++){
		scanf("%d%d%d", &tt, &ttt, &tttt);
		if (tt == 1) add(ttt, tttt);
		else printf("%d\n", sum(tttt) - sum(ttt - 1));
	}
}

树状数组的技巧

值域树状数组

我们可以将树状数组作为一个桶来使用。

具体的讲，就是每一次新增一个值 $x$ 时，执行 update(x, 1) 的操作；每一次删除一个值 $x$ 时，执行 update(x, -1) 的操作。利用树状数组的查询前缀和功能，我们可以快速回答，有多少个数的值域在 $[l, r]$ 中这样的问题。

当值域过大时，我们可以使用离散化来将数映射到 $[1, n]$ 的范围内，再进行下一步操作。

树状数组上倍增

当在使用树状数组的时候，我们经常会应对一些答案有单调性的问题（比如在值域树状数组上寻找第 $k$ 小）。

一种显然的解决方案就是使用二分，但是会增加一个 $\log$ 的时间复杂度，时间复杂度为 $O(\log^2 n)$ 。

有没有一种不增加时间复杂度的解决方案呢？当然是有的。

由于树状数组的每一个节点存储的都是一个长度为 $2$ 的整次幂的区间和，我们可以使用同样思想的倍增算法。

我们以值域树状数组上寻找第 $k$ 小为例。

我们设两个变量 $ans$ 与 $sum$ ，都初始化为 $0$ 。

然后，我们可以从 $\lfloor \log n \rfloor$ 倒序枚举 $p$ ，对于每一个 $p$ ，如果 $ans + 2^p \le n$ 且 $sum + s_{ans + 2^p} < k$ ， $ans \to ans + 2^p$ ， $sum \to sum + s_{ans + 2^p}$ 。

最后， $ans + 1$ 即为第 $k$ 小的值。由于倍增与树状数组相结合，可以直接在 $s$ 数组内查询，免去了调用查询操作的 $\log$ ，时间复杂度为 $O(\log n)$ 。

倍增查询第 $k$ 小代码：

int kth(int k){
	int p = 1, ans = 0, sum = 0;
	for (;(p << 1) <= n;p <<= 1);
	while (p){
		if (ans + p <= n && sum + s[ans + p] < k) ans += p, sum += s[ans];
		p >>= 1;
	}
	return ans + 1;
}

树状数组的拓展

区间修改单点查询

树状数组所擅长的是单点修改区间查询，如果我们把操作换成区间修改单点查询，该怎么办呢？

我们可以使用差分来解决这个问题。

$a$ 的差分数组 $b$ 满足以下条件：

$b_1 = a_1$ 。
对于 $2 \le i \le n$ ， $b_i = a_i - a_{i - 1}$ 。

我们可以发现， $\sum_{j = 1}^i b_j = a_i$ 。这样一来，我们想查询 $a_i$ 的时候，只需要查询 $b$ 数组的前缀和即可。

那修改怎么办呢？

我们假设 $n = 8$ ，要将 $[2, 5]$ 加上 $x$ 。

$a \to \{a_1, a_2 + x, a_3 + x, a_4 + x, a_5 + x, a_6, a_7, a_8\}$

$b \to \{b_1, b_2 + x, b_3, b_4, b_5, b_6 - x, b_7, b_8\}$

我们可以发现，对于差分序列 $b$ ，我们只需要使 $b_l \to b_l + x$ ， $b_{r + 1} \to b_{r + 1} - x$ 即可。

模板题二代码：

#include <cstdio>

using namespace std;

int n, m;
long long t[500001], ss, l, r;
char c;
long long lowbit(long long x){
	return x & -x;
}
long long sum(int i){
	long long s = 0;
	while (i > 0){
		s += t[i];
		i -= lowbit(i);
	}
	return s;
}
void add(int i, long long x){
	while (i <= n){
		t[i] += x;
		i += lowbit(i);
	}
}
int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1;i <= n;i ++) scanf("%lld", &r), add(i, r - l), l = r;
	for (int i = 1;i <= m;i ++){
		scanf(" %c", &c);
		if (c == '1') scanf("%d%d%lld", &l, &r, &ss), add(l, ss), add(r + 1, -ss);
		else scanf("%lld", &l), printf("%lld\n", sum(l));
	}
}

区间修改区间查询

考虑在区间修改单点查询的基础上继续升级。

如果单点查询 $a_x$ 的结果为 $\sum_{i = 1}^x b_i$ ，那查询区间 $[1, x]$ 的结果即为：

\sum_{i = 1}^x \sum_{j = 1}^i b_j

上式可以改写为：

\sum_{i = 1}^x (x - i + 1) \times b_i = (x + 1)\sum_{i = 1}^x b_i - \sum_{i = 1}^x i \times b_i

我们增加一个树状数组用来维护 $\sum_{i = 1}^x i \times b_i$ ，就可以用两个树状数组来实现区间修改区间查询了！（查询 $[l, r]$ 还是只需查询 $[1, r] - [1, l - 1]$ 即可）

模板题三代码：

#include <algorithm>
#include <cstdio>
#define ll long long
inline int lowbit(int x){return x & -x;}
struct BIT{
	int n;
	ll s[100001];
	void init(int x){
		n = x;
		for (int i = 1;i <= n;i ++) s[i] = 0;
	}
	void update(int p, ll x){
		while (p <= n) s[p] += x, p += lowbit(p);
	}
	ll query(int p){
		ll sum = 0;
		while (p) sum += s[p], p -= lowbit(p);
		return sum;
	}
}t1, t2;

using namespace std;

int n, m, op, l, r;
ll x;
int main(){
	scanf("%d%d", &n, &m);
	t1.init(n), t2.init(n);
	for (int i = 1;i <= n;i ++){
		scanf("%d", &r);
		t1.update(i, r - l), t2.update(i, 1ll * (r - l) * i);
		l = r;
	}
	while (m --){
		scanf("%d", &op);
		if (op == 1){
			scanf("%d%d%lld", &l, &r, &x);
			t1.update(l, x), t1.update(r + 1, -x);
			t2.update(l, 1ll * l * x), t2.update(r + 1, 1ll * (r + 1) * -x);
		}
		else {
			scanf("%d%d", &l, &r);
			ll L = 1ll * l * t1.query(l - 1) - t2.query(l - 1);
			ll R = 1ll * (r + 1) * t1.query(r) - t2.query(r);
			printf("%lld\n", R - L);
		}
	}
}

例题

菜王的 blog

树状数组学习笔记