【OI之路】02数据结构-2树状数组

6.2.0 前言

本文同样不是教程,提供一些思路罢了

6.2.1 定义

树状数组是一种利用正整数二进制的某种特殊性质,
从而比线段树更精简但没这么强大的,
并且借助了前缀和思路的特殊数组

6.2.2 有关二进制

基础知识可以参考这篇文章
主要就是这个函数,原理可以看网上的教程,
主要就是O(1)找到自己的父亲(加上结果)和兄弟(减去结果)

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

6.2.2 单点更新, 区间询问

前缀和:
i到j就是ask(j)-ask(i-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void change(int x,int c)
{
while(x<=n)
{
p[x]=c;
x+=lowbit(x);
//更新管理着x的所有父亲
}
}
int ask(int x)
{
int s=0;
while(x>=1)
{
s+=p[x];
x-=lowbit(x);
//加上自己所管理不到的,在我前面的兄弟
}
}

6.2.3 区间更新, 单点询问

运用差分
就是说原本的a[i]=p[1]+p[2]…+p[i]
从而把数值变得依赖于前面的数值

若要将a数组区间[l,r]的元素都加上key,
显然只需令p[l]+=key,p[r+1]-=key即可。

差分思想的运用灰常广泛,这只是其中一种简单的体现
详见Tag-差分

6.2.4 区间更新, 区间询问

假设现在求sum[s],d[]是差分数组
a[1]+a[2]+a[3]+…..+a[s-1]+a[s]
=(d[1])+(d[1]+d[2])+…..+(d[1]+d[2]+…..+d[s])
=(s)d[1]+(s-1)d[2]+…..+(1)d[s]
=s
(d[1]+d[2]+….+d[s])-((1-1)d[1]+(2-1)d[2]…+(s-1)d[s])
为了简化,故定义另一个数组c
c[i]=(i-1)
d[i]
从而把原式化简为
=s*(d[1]+d[2]+….+d[s])-(c[1]+c[2]…+c[s])

这样,只需要两个树状数组即可,一个维护d,一个维护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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<cstdio>
#include<algorithm>
using namespace std;
//*******************定义*******************
typedef long long ld;
ld n;ld c[2][210000];
//*******************实现*******************
ld lowbit(ld x)
{
return x&-x;
}
void ch(ld f,ld x,ld s)
{
while(x<=n)
{
c[f][x]+=s;
x+=lowbit(x);
}
}
ld sum(ld f,ld x)
{
ld s=0;
while(x>0)
{
s+=c[f][x];
x-=lowbit(x);
}
return s;
}
//*******************接口*******************
ld ask(ld x)
{
return x*sum(0,x)-sum(1,x);
}
//*******************主函数*******************
ld a[210000];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
ld d=a[i]-a[i-1];
ch(0,i,d);
ch(1,i,(i-1)*d);
}
int q;scanf("%d",&q);
while(q--)
{
int o,a,b;scanf("%d%d%d",&o,&a,&b);
ld c;
if(o==1)
{
scanf("%lld",&c);
//d[i]+=c
ch(0,a,c);ch(0,b+1,-c);
//c[i]+=(i-1)*c
ch(1,a,(a-1)*c);ch(1,b+1,-b*c);
}
else printf("%lld\n",ask(b)-ask(a-1));
}
}

可以去Codevs1082评测
如果用线段树就灰常简单了:这篇文章

6.2.4 练习题

Tag-树状数组

6.2.5 总结

树状数组的核心竞争力在于比线段树容易实现(因为利用前缀和思想),
但也正是因为用了前缀和,操作必须满足区间可加性,例如无法求最值

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/1650.html
转载请注明出处,谢谢!