信竞学习笔记：树状数组

Tiger

发表于 2026-07-20

更新于 2026-07-20

14 2.1~2.7 分钟 937

注：这是本人的课堂笔记。

树状数组用于维护可单点修改的前缀和，也就是单点修改、区间查询。

单点修改、区间查询

例题：P3374

树状数组核心是利用二进制，首先我们要有一个 $\operatorname{lowbit}$ 函数，获取一个数二进制表示中的最低的为 $1$ 的位的十进制表示：

int lowbit(int x) {
    return x & (-x); // 原理：补码
    // 关于原理，读者可自行查阅资料，这里不再详细说明
}

我们维护一个数组 $c$ 来存储树状数组，设原数组为 $a$ ，则：

c_i = \sum\limits_{j=i-\operatorname{lowbit}(i)+1}^i a_j

也就是说，树状数组中每个位置 $c_x$ 保存的是从 $x$ 向前 $\operatorname{lowbit}(x)$ 长度的区间和。

要求 $[1, x]$ 区间的前缀和，考虑先将 $c_x$ 加入大安，剩下的部分就是 $[1, i-\operatorname{lowbit}(i)]$ 。对于这一部分，我们可以重复上面操作，直至问题变为求 $s_0 = 0$ 为止。于是，我们可以写出如下代码：

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

要进行单点修改，考虑如何将 $a_x$ 加上 $y$ 。由于 $c$ 中有多个位置包含 $a_x$ ，这些位置都要进行修改。

考虑上面区间查询的过程，是从区间推到单点，我们是否能够反过来，从单点推到区间。考虑按照 $\operatorname{lowbit}(i)$ 从小到大找出包含 $a_x$ 的 $c_i$ 。不断将下标 $i$ 加上 $\operatorname{lowbit}(i)$ ，并在过程中对每个 $c_i$ 进行修改。于是，我们可以写出如下代码：

void add(int x, int y) {
    for (int i=x; i<=n; i+=lowbit(i)) c[i] += y;
}

区间修改、单点查询

例题：P3368

要实现区间修改、单点查询，我们可以用树状数组维护一个差分数组，这样就可以快速地进行区间修改和单点查询。

树状数组模板与前面相同，主函数修改如下：

int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr); // 关同步流
	
	cin >> n >> m;
	
	for (int i=1; i<=n; i++) {
		cin >> a[i];
		add(i, a[i] - a[i-1]);
	}
	
	while (m--) {
		int op, x, y, k;
		cin >> op >> x;
		if (op == 1) {
			cin >> y >> k;
			add(x, k);
			add(y + 1, -k);
		}
		else {
			cout << sum(x) << '\n';
		}
	}
	
	return 0;
}

权值树状数组

例题：P1908

权值树状数组对每个数的权值进行维护，例如本题求逆序对需要对数出现的次数进行维护。

对于一个序列 $a$ ，逆序对指 $i < j$ 且 $a_i > a_j$ 的有序对。要求逆序对的个数，实际上就是求：对于每个 $i$ ， $i < j$ 且 $a_i > a_j$ 的有序对的个数的和。

设所有 $j > i$ 中 $a_j = k$ 的数量为 $t_k$ ，则对于下标 $i$ ，这个位置上逆序对的个数即为：

s_{a_i-1} = \sum\limits_{k=1}^{a_i-1} t_k

注意到此时，我们查询的是数组 $t$ 的前缀和。按从大到小的顺序枚举 $i$ ，先查询，再更新。在每次查询过后，需要将 $t_{a_i}$ 增加 $1$ 。统计每次查询的和即可。区间查询和单点修改操作使用树状数组实现。

由于本题数据范围较大，需要使用离散化缩减空间。

树状数组模板同上。主函数代码如下：

int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	cin >> n;
	
	for (int i=1; i<=n; i++) {
		cin >> a[i];
		b[i] = a[i]; // 离散化需要使用另外的 O(n) 空间
	}
	
	sort(b+1, b+n+1);
	m = unique(b+1, b+n+1) - b - 1; 
	
	for (int i=n; i; i--) {
		int k = lower_bound(b+1, b+m+1, a[i]) - b;
		ans += sum(k - 1);
		add(k, 1);
	} 
	
	cout << ans;
	
	return 0;
}