HackPluto's Blog

树状数组

字数统计: 1.9k阅读时长: 8 min
2019/10/28 Share

引入

这里通过一个简单的题目展开介绍,先输入一个长度为n的数组,然后我们有如下两种操作:

  • 输入一个数m,输出数组中下标1~m的前缀和
  • 对某个指定下标的数进行值的修改
    多次执行上述两种操作

普通方法
对于一个的数组,如果需要求1~m的前缀和我们可以将其从下标1开始对m个数进行求和,对于n次操作,时间复杂度是O(n^2),

1
2
for i 1 -> m
sum += num[i]

对于值的修改,我们可以直接通过下标找到要修改的数,n次操作时间复杂度为O(n),在数组n开得比较大的时候,求前缀和的效率显得低了

优化的方式:
初始我们用一个数组A的保存每个位置的初始值,然后用一个辅助数组B存放的是下标为i的时候A数组的前i个的和(前缀和),那么当我们需要查询m个数的前缀和的时候只要直接使用下标对B数组进行查询即可,

1
2
for i 1 -> m
b[i] = b[i-1] + num[i]

n次查询,时间复杂度为O(n),而此时,对于单点更新值的维护消耗,由原来的O(n)变成了O(n^2),因为每一次与更新单点值都会对后面的已经计算好的B数组前缀和的值造成影响,需要不断更新B数组的值,n次更新维护的消耗自然就变成了O(n ^ 2),更新的效率变得低下.

树状数组

这里将介绍树状数组如何处理前缀和查询和单点更新的问题,对于n次操作,时间复杂度都为O(nlogn)

对于一个长度为n的数组,A数组存放的是数组的初始值,引入一个辅助数组C(我们通过C数组建立树状数组)
C1 = A1
C2 = C1 + A2 = A1 + A2
C3 = A3
C4 = C2 + C3 + A4 = A1 + A2 + A3 + A4
C5 = A5
C6 = C5 + A6 = A5 + A6
C7 = A7
C8 = C4 + C6 + C7 + A8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

求前缀和

我们称C[i]的值为下标为i的数所管辖的数的和,C[8]存放的就是被编号8所管辖的那些数的和(有8个),而下标为i的数所管辖的元素的个数则为2^k个(k为i的二进制的末尾0的个数)举两个例子查询下标m=8和m=5所管辖的数的和

而对于输入的数m,我们要求编号为m的数的前缀和A1 ~ Am(这里假设树状数组已经建立,即C1~C8的值已经求出)举两个例子m=7和m=6(sum(i)表示求编号为i的前缀和)

  • m=7 sum(7) = C7 + C6 + C4
    对于查询的m,将它转换成二进制后,不断对末尾的1的位置进行-1的操作,直到全部为0停止
    7的二进制为0111(C7得到),那么先对0111的末尾1的位置-1,得到0110 == 6(C6得到),再对0110末尾1位置-1,得到0100 == 4(C4得到),最后对0100末尾1位置-1后得到0000(结束信号),计算停止,至此C7,C6,C4全部得到,求和后就是m == 7时它的前缀和
  • m=6 sum(6) = C6 + C4
    m = 6时也是一样,先转成2进制等于0110,经过两次变换后为0100(C4)和0000(结束信号),那么求和后同样也得到了预计的结果

这里要介绍一个高效的方法,lowbit(int m),这是一个函数,它的作用是求出m的二进制表示的末尾1的位置,对于要查询m的前缀和,m = m - lowbit(m)代表不断对二进制末尾1进行-1操作,不断执行直到m == 0结束,就能得到前缀和由哪几个Cm构成,十分巧妙,lowbit也是树状数组的核心

1
2
3
int lowbit(int m){
return m&(-m);
}

求前缀和的代码

1
2
3
4
5
6
7
int ans = 0;
int getSum(int m){
while(m > 0){
ans += C[m];
m -= lowbit(m);
}
}

更新点的值

设x=2,value=5,那么我们先找到A[2]的位置,通过观察我们得知,如果修改了A[2]的值,那么管辖A[2]的C[2],C[4],C[8]的前缀和都要加上value(所有的祖先节点),那么和查询类似,我们如何得到C2的所有祖先节点呢(因为C2和A2的下标相同所以更新时查询从C[x]开始),依旧是上述的巧妙的方法,但是我们把它倒过来
对于要更新x位置的值,我们把x转换成二进制,不断对二进制最后一个1的位置+1,直到达到数组下标的最大值n结束
对于给出的例子x=2,假设数组下标上限n=8,x转换成二进制后等于0010(C2),对末尾1的位置进行+1,得到0100(C4),对末尾的1的位置进行+1,得到1000(C8),循环结束,对C2,C4,C8的前缀和都要加上value,当然不能忘记对A[2]的值+value,单点更新值过程结束
给出代码

1
2
3
4
5
6
7
void update(int x, int value){
A[x] += value;
while(x <= n){
C[x] += value;
x += lowbit(x);
}
}

构建树状数组

事实上,对于一个输入的数组A,我们一次读取的过程,就可以想成是一个不断更新值的过程(把A1~An从0更新成我们输入的A[i]),所以一边读入A[i],一边将C[i]涉及到的祖先节点值更新,完成输入后树状数组C也就建立成功了

完整代码如下:

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
#include<stdio.h>
#include<string.h>
int a[10005];
int c[10005];
int n;
int lowbit(int x){
return x&(-x);
}

int getSum(int x){
int ans = 0;
while(x > 0){
ans += c[x];
x -= lowbit(x);
}
return ans;
}

void update(int x, int value){
a[x] += value;
while(x <= n){
c[x] += value;
x += lowbit(x);
}
}

int main(){
while(scanf("%d", &n)!=EOF){
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
update(i, a[i]);
}
int ans = getSum(n-1);
printf("%d\n", ans);
}
return 0;
}

例题

Ping pong

这个题就是一个应用树状数组的题,题的是要求在A,B两点间介于两者值之间数的个数,如果使用朴素的暴力解法,求出n个点所有的情况,最后的时间复杂度O(n ^ 3),这显然是会超时的。这个题可以换一个思路,转而去研究对于第i个人当裁判,假设i左边比i小的是a个人,i右边比i大的是b人,对于i的解法数就是a b+(i-1-a) (n-i-b)。那么在更新树状数组的时候,就把a[i]的值加1更新,再统计sum(i)是多少就知道了i左边多少个数比i小

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
#include<iostream>
#include<string.h>
using namespace std;
int c[1005];
int t;
int n;
int a[1005];
int s1[1005];
int s2[1005];
int lowbit(int x){
return x&-x;
}

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

void add(int x,int d){
while(x<=1005){
c[x]+=d;
x+=lowbit(x);
}
}

int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++){
add(a[i],1);
s1[i]=sum(a[i]-1);
}
memset(c,0,sizeof(c));
for(int i=n;i>=1;i--){
add(a[i],1);
s2[i]=sum(a[i]-1);
}
long long ans=0;
for(int i=2;i<=n;i++){
ans+=s1[i]*(n-i-s2[i])+(i-s1[i]-1)*s2[i];
}
cout<<ans<<endl;
}
return 0;
}






CATALOG
  1. 1. 引入
  2. 2. 树状数组
    1. 2.1. 求前缀和
    2. 2.2. 更新点的值
    3. 2.3. 构建树状数组
  3. 3. 例题
    1. 3.1. Ping pong