树状数组(Binary Indexed Tree)

12 Sep 2025

1.简介

普通的树状数组可以处理单点修改和区间查询。
树状数组维护的信息必须满足结合律和可差分（如加法，乘法，异或）。
利用差分，可以实现区间修改。

2.原理

将一段长度为n的区间拆成不多于logn段区间。

fenwick

这样处理各种问题效率要更高。如计算a[1…7]的和，过程：从c[7]开始往前跳，发现c[7]只管辖a[7]这个元素；然后找到c[6]，发现c[6]管辖a[5…6]；然后找到c[4]，发现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]。

2.2 lowbit原理

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

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

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

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

计算结果和正确答案差了1，所以引申出补码的概念来解决问题。

补码：正数的补码是其原码，负数的补码是其原码+1。

lowbit(x) = x & -x，-x在运算过程中，其形式是补码（存储过程中也是）。

通过这样的运算，可以得到最低位的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)。

时间复杂度:

对于查询操作，最坏情况是将这个数组c遍历一遍，所需时间O(log n)。因为将长度为n的数列为成了log n个区间。
对于修改操作，点x的高度为log2 (lowbit(x))，不会超过log 2 n, 同样是log级别：O(log n)。

5.例题

Example 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;
}

Example 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;
}

Example 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。观察桶数组，5,4,6这三个数字在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 m = 1;
for(int i = 1; i <= n; i++)
        if(b[i] != b[i-1]) 
                c[j++] = b[i]; // 去重
m--;
for(int i = 1; i <= n; i++)
        a[i] = lower_bound(c+1, c+j+1, a[i]) - c;

解释:

a数组为原数组，存储了原始值。不能直接在a数组上操作，因为生成索引后，还要根据原始值的大小，来决定分到哪个索引。要保持元素的顺序不变。
将b数组排序、去重后得到了c数组。排序是为了得到索引。去重可以优化离散化。比如，有1000个相同的数，如果不去重，那么将会生成1000个索引。但是去重后只用生成1个即可。
对于每个a[i]，在c数组中找到它的位置。lower_bound(f.begin, f.end, value)，就是在数组f的区间[f.begin, f.end]中，找到第一个大于或等于value的元素。
减去c（数组首地址）得到该元素在c数组中的索引。

一个例子：

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

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

树状数组(Binary Indexed Tree)

Related Posts