首页 > 代码库 > 树状数组基础
树状数组基础
关于树状数组的讲解推荐《算法竞赛入门经典训练指南》
一维版本:
洛谷3374
链接:https://www.luogu.org/problem/show?pid=3374
分析:树状数组裸的模板题
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int maxn=500000+10; 6 int c[maxn]; 7 int n,m; 8 int lowbit(int x){ 9 return x&(-x); 10 } 11 void add(int x,int d){ 12 while(x<=n){ 13 c[x]+=d; x+=lowbit(x); 14 } 15 } 16 int sum(int x){ 17 int ret=0; 18 while(x>0){ 19 ret+=c[x]; x-=lowbit(x); 20 } 21 return ret; 22 } 23 int main() 24 { 25 cin>>n>>m; 26 memset(c,0,sizeof(c)); 27 for(int i=1;i<=n;i++){ 28 int x; 29 scanf("%d",&x); 30 add(i,x); 31 } 32 while(m--){ 33 int num,a,b; 34 scanf("%d%d%d",&num,&a,&b); 35 if(num==1){ 36 add(a,b); 37 }else{ 38 printf("%d\n",sum(b)-sum(a-1)); 39 } 40 } 41 return 0; 42 }
二维版本:
vijos1512
链接:https://vijos.org/p/1512
分析:二维树状数组的裸题,注意面积的计算
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<cmath> 6 using namespace std; 7 const int maxn=2000; 8 int c[maxn][maxn]; 9 int n,m; 10 int lowbit(int x){ 11 return x&(-x); 12 } 13 void add(int x,int y,int d){ 14 for(int i=x;i<=n;i+=lowbit(i)) 15 for(int j=y;j<=n;j+=lowbit(j)) 16 c[i][j]+=d; 17 } 18 int sum(int x,int y){ 19 int ret=0; 20 for(int i=x;i>0;i-=lowbit(i)) 21 for(int j=y;j>0;j-=lowbit(j)) 22 ret+=c[i][j]; 23 return ret; 24 } 25 int main() 26 { 27 scanf("%d",&n); 28 memset(c,0,sizeof(c)); 29 while(scanf("%d",&m)!=EOF){ 30 if(m==3) break; 31 if(m==1){ 32 int x,y,k; 33 scanf("%d%d%d",&x,&y,&k); 34 add(x+1,y+1,k); 35 }else{ 36 int x1,y1,x2,y2; 37 scanf("%d%d%d%d",&x1,&y1,&x2,&y2); 38 int cnt=sum(x2+1,y2+1)-sum(x1,y2+1)-sum(x2+1,y1)+sum(x1,y1); 39 printf("%d\n",cnt); 40 } 41 } 42 return 0; 43 }
树状数组基础
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。