Top

树状数组


树状数组是一个查询和修改复杂度都为log(n)的数据结构。主要用于数组的单点修改&&区间求和.

另外一个拥有类似功能的是线段树.1.两者在复杂度上同级, 但是树状数组的常数明显优于线段树, 其编程复杂度也远小于线段树.

2.树状数组的作用被线段树完全涵盖, 凡是可以使用树状数组解决的问题, 使用线段树一定可以解决, 但是线段树能够解决的问题树状数组未必能够解决.

3.树状数组的突出特点是其编程的极端简洁性, 使用lowbit技术可以在很短的几步操作中完成树状数组的核心操作,其代码效率远高于线段树。

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
//hdu1166
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int maxn=50007;
int a[maxn];
int tree[maxn],n;
int lowbit(int x){
return x&(-x);
}
void add(int x,int v){ //改
while(x<=n){
tree[x]+=v;
x+=lowbit(x);
}
}
int query(int x){ //查
int sum=0;
while(x){
sum+=tree[x];
x-=lowbit(x);
}
return sum;
}
int main(){
int t,tt=1;
scanf("%d",&t);
while(tt<=t){
memset(tree,0,sizeof(tree));
printf("Case %d:\n",tt++);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
add(i,a[i]);
}
char cmd[10];
int l,r;
while(scanf("%s",cmd)){
if(cmd[0]=='E')break;
scanf("%d%d",&l,&r);
if(cmd[0]=='Q'){
printf("%d\n",query(r)-query(l-1));
}
else if(cmd[0]=='A'){
add(l,r);
}
else if(cmd[0]=='S'){
add(l,-r);
}
}
}
return 0;
}
文章版权为Anoyer博客所有,转载请以链接形式标明本文地址