树状数组

一种查询和修改复杂度都为 $\log(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
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<cstdio>
const int N = 500000+10;
int C[N];
int n;
int lb(int i)
{
return i&-i;
}
void add(int i,int k)//A[i]+=k,A为原数组
{
while(i <= n)
{
C[i] += k;
i += lb(i);
}
return;
}
int sum(int i)
{
int ans = 0;
while(i > 0)
{
ans += C[i];
i -= lb(i);
}
return ans;
}
int main()
{

int m;
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i ++)
{
int x;
scanf("%d",&x);
add(i,x);
}
int t,a,b;
for(int i = 1;i <= m;i ++)
{
scanf("%d%d%d",&t,&a,&b);
if(t == 1)
{
add(a,b);
}
else if(t == 2)
{
int res = sum(b) - sum(a-1);
printf("%d\n",res);
}
}
return 0;
}

区间修改+单点查询

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
#include<cstdio>
const int N = 500000+10;
int C[N];
int n;
int lb(int i)
{
return i&-i;
}
void add(int i,int k)
{
while(i <= n)
{
C[i] += k;
i += lb(i);
}
return;
}
long long qeury(int i)
{
long long ans = 0;
while(i > 0)
{
ans += C[i];
i -= lb(i);
}
return ans;
}
int main()
{
int m;
scanf("%d%d",&n,&m);
int now,last = 0;
for(int i = 1;i <= n;i ++)
{
scanf("%d",&now);
add(i,now-last);
last = now;
}
int t,a,b,k;
for(int i = 1;i <= m;i ++)
{
scanf("%d",&t);
if(t == 1)
{
scanf("%d%d%d",&a,&b,&k);
add(a,k);
add(b+1,-k);
}
else if(t == 2)
{
scanf("%d",&a);
long long res = qeury(a);
printf("%lld\n",res);
}
}
return 0;
}