树状数组

发表于 | 分类于

树状数组的基本用途是维护序列的前缀和

树状数组支持的基本操作：

  • 查询前缀和
  • 单点修改

lowbit运算讲解

lowbit(n)定义为非负整数n在二进制表示下“最低位的1及后面所有的0”构成的数值。例如n=10的二进制表示为1010，则lowbit(10) = 2。下面我们来推导lowbit(n)公式的推导:

设n>0，n的第k位是1，第0~k-1位都是0

为了实现lowbit运算，先把n取反，此时第k位变为0，第0~k-1位都是1。再令n=n+1，此时因为进位，第k位变为1，第0~k-1位都是0。

在上面的取反加1操作后，n的第k+1位到最高位恰好与原来相反，所以 n&(~n+1)仅有第k位为1，其余为都是0，而在补码表示下，~n=-1-n，因此：

                    lowbit(n) = n & (~n + 1) = n & (-n)

附上线段树模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#define max(x, y) ((x) > (y) ? (x) : (y))
int n, m, tree[100000 + 5];
inline int lowbit(int x) {
	return x & -x;
}
inline void add(int k, int a) {
	while(k <= n) {
		tree[k] += a;
		k += lowbit(k);
	}
}
inline int read(int k) {
	int sum = 0;
	while(k) {
		sum += tree[k];
		k -= lowbit(k);
	}
	return sum;
} 
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		int x; scanf("%d", &x);
		add(i, x);
	}
	scanf("%d", &m);
	for(int i = 1; i <= m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		if(x == 1) {add(y, z);}
		else {printf("%d\n", read(z) - read(y - 1));}
	}
	return 0;
}