DragonDreamYF > 树状数组的学习

树状数组的学习

2019-07-17

树状数组

树状数组的学习

当然作为蒟蒻的我也仅仅是才开始学习QAQ

咳咳，下面进入正文qwq：

当然，在进行树状数组的运用之前，要先了解一下何为树状数组。

树状数组是什么？

数组如其名，它就是一个树状的数组（类似于二叉树好吧就是）

对于 a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8].

我们定义

c[1] = a[1]

c[2] = a[1] + a[2]

c[3] = a[3]

c[4] = a[1] + a[2] + a[3] + a[4]

c[5] = a[5]

c[6] = a[5] + a[6]

c[7] = a[7]

c[8] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8]

此处不贴图我感觉反而方便理解

于是，我们大胆地将其转换成二进制ヾ(≧▽≦)o

c[1] = c[0001] = a[1]

c[2] = c[0010] = a[1] + a[2]

c[3] = c[0011] = a[3]

c[4] = c[0100] = a[1] + a[2] + a[3] + a[4]

c[5] = c[0101] = a[5]

c[6] = c[0110] = a[5] + a[6]

c[7] = c[0111] = a[7]

c[8] = c[1000] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8]

c[i] = a[i - 2 ^ k + 1] + a[i - 2 ^ k + 2] + …… +a[i]

k 为 i 的二进制中从最低位到第一个高位 “1” 的连续零的长度

i = 8 (1000) 时 k = 3

我们知道,对于一个数的负数就等于对这个数取反+1

以二进制数11010为例:11010的补码为00101,加1后为00110,两者相与便是最低位的1

其实很好理解,补码和原码必然相反,所以原码有0的部位补码全是1,补码再+1之后由于进位那么最末尾的1和原码

最右边的1一定是同一个位置(当遇到第一个1的时候补码此位为0,由于前面会进一位,所以此位会变为1)

所以我们只需要进行a&(-a)就可以取出最低位的1了

于是

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

单点修改

因为这是一个树状的数组，所以在对 a[i] 进行更新时，必定会同步更新 c 数组

1(001) c[1] += a[1]

lowbit (1)= 001 = 1 + lowbit(1) = 2(010) c[2] += a[1]

lowbit (2)= 010 = 2 + lowbit(2) = 4(100) c[4] += a[1]

lowbit (4)= 100 = 4 + lowbit(4) = 8(1000) c[8] += a[1]

1
2
3
4
5
void update (int x, int y) {
    for (int i = x; i <= n; i += lowbit (i)) {
		c[i] += y ;
   	}
}

区间查询

emmmm…… 对于区间查询，呃，我实在是没有觉得有什么好说的

自己手推一下就出来了（然而花了我十多分钟QAQ）

说白了，区间查询就是单点修改的逆操作

因为是树状数组，所以每一个 c[] 对应着一段 a[] 或 一个 a[] 的和

举例来说，当我想求2 ~ 5的区间和时，我需要先求1 ~ 2的区间和，再求1 ~ 5的区间和，然后作差

即

1
cout<<getsum(5) - getsum(2)<<endl ;
1
2
3
4
5
6
int getsum (int x) {
	int ans = 0 ;
	for (int i = x; i; i -= lowbit (i))
		ans += c[i] ;
	return ans ;
}

既然都已经会了，那么开始做题吧qwq

HDU1166 敌兵布阵

嘛，没做完不许看

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std ;
int c[50001] ;
int n, t ;
string s ;
int lowbit (int i) {
	return i & (-i) ;
}
void update (int x, int y, int n) {
	for (int i = x; i <= n; i += lowbit(i))
		c[i] += y ;
}
int getsum (int x) {
	int ans = 0 ;
	for (int i = x; i != 0; i -= lowbit(i)) {
		ans += c[i] ;
	}
	return ans ;
}
int main() {
	cin>>t ;
	for (int k = 1; k <= t; ++k) {
		cout<<"Case "<<k<<":"<<endl ;
		cin>>n ;
		memset (c, 0, n + 1 << 2) ; // 巨坑无比，我在这个点上卡了三次，全是超时
		// 切记不要 memset (c, 0, sizeof (c)) ;
		// 否则你会死的很难看QAQ
		for (int  i = 1; i <= n; i++) {
			int z ;
			cin>>z ;
			update (i, z, n) ;
		}
		while (1) {
			cin>>s ;
			int x, y ;
			if (s[0] == 'E') {
				break ;
			}
			if (s[0] == 'A') {
				cin>>x>>y ;
				update (x, y, n) ;
				continue ; // 这是习惯，可加可不加
			}
			if (s[0] == 'S') {
				cin>>x>>y ;
				update (x, -y, n) ;
				continue ;
			}
			if (s[0] == 'Q') {
				cin>>x>>y ;
				cout<<getsum (y) - getsum (x - 1)<<endl ;
				continue ;
			}
		}
	}
	return 0 ;
}

代码巨丑，请见谅（反正我也没有评论功能，有本事来打我呀）

进阶篇——-关于差分与树状数组

本博主其实也不大会啦qwq(￣▽￣)”，所以对于听懂不要抱太大希望

对于本部分可以去看一下Dy大佬的blog

RisingSunLight

差分