树状数组

12 Sep 2025

1. 简介

普通树状数组可以处理单点修改和区间查询。
树状数组维护的运算需满足结合律，并能通过逆运算还原区间结果。例如加法和异或满足该条件；乘法则要求相关元素可逆。
结合差分数组，可以实现区间修改。

2. 原理

将长度为 n 的前缀区间拆分为不超过 log n 段区间。

fenwick

这样可以更高效地处理各种问题。以计算 a[1…7] 的和为例：从 c[7] 开始向前跳，c[7] 只管辖 a[7]；接着到 c[6]，它管辖 a[5…6]；再到 c[4]，它管辖 a[1…4]。下一步会到 c[0]，但该节点不存在，因此停止。答案为 c[7] + c[6] + c[4]。

如果查询的是a[4…7]，那么答案是：查询a[1…7] - 查询a[1…3]。

2.1 管辖区间

问题是，c[x]管辖的区间长度到底是多少（向左边延伸多长）？

规定 c[x] 管辖的区间长度为 2 的 k 次方，其中：

k 表示 x 的二进制表示中最低位 1 所在的位置。
2 的 k 次方表示 x 的二进制表示中，由最低位 1 及其后所有 0 构成的数的十进制值。

比如，c[88]管辖的区间长度：

88(10) = 01011000(2)，其中最低位的1和后面的0组成的数字为1000(2)，即8(10)，所以长度为8，c[88]管辖a[81…88]。

可以用 lowbit(x) 求 x 的二进制表示中最低位 1 及其后的 0 所构成的数。lowbit(x) 的十进制值为 2 的 k 次方，也就是区间长度，因此 c[x] 管辖的区间为 a[x-lowbit(x)+1…x]。

2.2 lowbit 原理

原码：最简单的机器数表示法。最高位为符号位，1 表示负数，0 表示正数，其余位存放该数的二进制绝对值。

反码：正数的反码是其原码；负数的反码是其原码除符号位外按位取反。

1110(-1) + 1101(-2) = 1011(-4)，而正确答案应该是-3;

1110(-1) + 1100(-3) = 1010(-5)，而正确答案应该是-4。

计算结果与正确答案相差 1，因此引入补码来解决这一问题。

补码：正数的补码是其原码；负数的补码是其反码加 1。

lowbit(x) = x & -x。在补码表示中，-x 可由 x 按位取反后加 1 得到。

通过这一运算，可以得到最低位的 1 及其后所有 0 构成的数。

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

3. 实现

3.1 区间查询

对于区间 [L, R] 的查询，都可以拆解为 [1, L-1] 与 [1, R] 的查询，再用后者减去前者。

具体过程：查询 a[1…x] 的和。

从 c[x] 向前跳，累加 c[x] 管辖的区间 a[x-lowbit(x)+1…x]；
令 x -= lowbit(x)。若 x = 0，说明已经跳到尽头；
将经过的 c 值相加。

int query(int x) {
  	int sum = 0;
  	while(x >= 1) {
		sum += c[x];
    		x -= lowbit(x);
  	}
  	return sum;
}

3.2 单点修改

对于长度为 n 的数列，修改第 x 个元素不仅会影响该元素本身，还会影响所有包含它的 c 区间。

那么从第x个元素开始，找到所有包含此元素的c，都进行修改。

void update(int x, int k) { // 将第x个元素加上k
  	while(x <= n) {
  	  	c[x] += k;
		x += lowbit(x);
	}
}

4. 复杂度

空间复杂度为O(n)。

时间复杂度：

对于查询操作，最多访问 O(log n) 个区间，因为长度为 n 的前缀会被拆分为 O(log n) 段；
对于修改操作，每次加上 lowbit(x) 都会跳到更高层的区间，最多访问 O(log n) 个节点。

5. 例题

示例 1：洛谷 P3374 模板 1

单点修改、区间求和，模板代码如下。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, a;
int t[500010];
int lowbit(int x) {
	return x & (-x);
}
void update(int x, int k) {
	while(x <= n) {
	  	t[x] += k;
		x += lowbit(x);
	}
}
int query(int x) {
	int sum = 0;
	while(x >= 1) {
	  	sum += t[x];
		x -= lowbit(x);
	}
	return sum;
}
signed main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
	  	cin >> a;
		update(i, a);
	}
	int op, x, y;
	while(m--) {
	  	cin >> op;
		if(op == 1) {
		  	cin >> x >> y;
			update(x, y);
		} else {
			cin >> x >> y;
			cout << query(y) - query(x-1) << "\n";
	 	}
	}
	return 0;
}

示例 2：洛谷 P3368 模板 2

区间修改，单点查询。要用到差分的思想。

a[] 1  5  4  2  3
d[] 1  4 -1 -2 -1

在区间 [2, 4] 中的每个元素都加上 2：若使用普通差分，则 d[2] += 2，d[5] -= 2。

如何与树状数组结合？将原数组转化为差分数组后，在差分数组上操作，此题就与模板 1 无异。在差分数组上单点修改，再求 [1…x] 的区间和，即可得到第 x 个元素的值。

三个函数与模板 1 相同；主函数的不同之处在于先将原数组转化为差分数组。

int main() {
        input();
  	
        d[1] = a[1];
        for(int i = 2; i <= n; i++) // 差分
                d[i] = a[i] - a[i-1];
  	
        for(int i = 1; i <= n; i++) // 差分数组上建树
                update(i, d[i]);
  	
        int op, x, y, k;
        while(m--) {
                cin >> op;
                if(op == 1) {
                        cin >> x >> y >> k;
                        update(x, k);
                        update(y+1, -k); // 利用差分来修改
                } else {
                        cin >> x;
                        cout << query(x) << "\n";
                }
        }
        return 0;
}

示例 3：洛谷 P1908 逆序对

题意：对于长度为 n 的数列，统计每个元素左侧比它大的元素数量。

input						output
6						11
5 4 2 6 3 1

思路：维护一个桶数组，记录每个数字出现的次数。依次读入数列元素，求出当前元素的贡献后，再将其放入桶数组。

例如，一个桶数组如下（原数组即为样例）：

i   1 2 3 4 5 6
t[] 0 1 1 1 1 1

此时刚刚将 3 放入数组。除 1 外，每个数字都出现过 1 次。现在计算 3 的贡献：已出现的数字中，5、4、6 均比 3 大，因此贡献为 3。观察桶数组可知，这些数字对应的位置都在 3 之后；将对应桶值相加，即 t[4] + t[5] + t[6] = 3。这是区间求和问题，可以使用树状数组。

因为将元素从左到右依次读入，所以桶数组所记录的，只是已读入的数组。当前元素右边的数仍未读入，所以不会影响答案（答案求的是，对于一个元素，求左边比它大的元素的个数）。

不过，桶数组有一个常见问题：数列中的数字可能达到 1e9，无法直接按值开桶，因此需要离散化。

for(int i = 1; i <= n; i++)
        cin >> a[i], b[i] = a[i];
sort(b+1, b+1+n);
int cnt = 0;
for(int i = 1; i <= n; i++)
        if(i == 1 || b[i] != b[i-1])
                c[++cnt] = b[i]; // 去重
for(int i = 1; i <= n; i++)
        a[i] = lower_bound(c+1, c+cnt+1, a[i]) - c;

解释：

a 数组保存原始值。离散化后仍需保持元素原有顺序，因此不能直接在 a 数组上排序；
将 b 数组排序、去重后得到 c 数组。排序用于建立排名，去重可减少排名数量；
对每个 a[i]，在 c 数组中找到对应位置。lower_bound(c+1, c+cnt+1, a[i]) 返回第一个大于或等于 a[i] 的元素位置；
减去 c 的首地址，即得到该元素在 c 数组中的下标。

例如：

原数组 60  100 40  30  200
离散化 3   4   2   1   5

在离散化后的数组上使用上述思路，即可解决此题。

树状数组

Related Posts