敌兵布阵 线段树（树状数组）

本文主要是介绍敌兵布阵 线段树（树状数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接
小小的模板题
线段树：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int tree[200101];
int n;
void build(int l,int r,int p)
{if(l==r){scanf("%d",&tree[p]);return ;}int mid=(l+r)>>1;build(l,mid,p<<1);build(mid+1,r,p<<1|1);tree[p]=tree[p<<1]+tree[p<<1|1];
}
void update(int l,int r,int x,int p,int val)
{if(l==r&&l==x){tree[p]+=val;return;}int mid=(l+r)>>1;if(x<=mid)update(l,mid,x,p<<1,val);elseupdate(mid+1,r,x,p<<1|1,val);tree[p]=tree[p<<1]+tree[p<<1|1];
}
int query(int l,int r,int L,int R,int p)
{if(L>r||R<l)return 0;if(L<=l&&R>=r)return tree[p];int mid=(l+r)>>1;int ans=0;//if(L<=mid)ans+=query(l,mid,L,R,p<<1);//if(R>mid)ans+=query(mid+1,r,L,R,p<<1|1);return ans;
}
int main()
{int t,k=1;scanf("%d",&t);while(t--){scanf("%d",&n);build(1,n,1);printf("Case %d:\n",k++);char a[100];while(~scanf("%s",a)){if(strcmp(a,"End")==0)break;if(a[0]=='A'){int x,y;scanf("%d%d",&x,&y);update(1,n,x,1,y);}else if(a[0]=='S'){int x,y;scanf("%d%d",&x,&y);update(1,n,x,1,-y);}else if(a[0]=='Q'){int x,y;scanf("%d%d",&x,&y);printf("%d\n",query(1,n,x,y,1));}}}return 0;
}

树状数组：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int tree[200020],n;
int lowbit(int x)
{return x&(-x);
}
void ad(int x,int val)
{while(x<=n){tree[x]+=val;x+=lowbit(x);}
}
int getsum(int x)
{int sum=0; while(x>0){sum+=tree[x];x-=lowbit(x);}return sum;
}
int main()
{int t;scanf("%d",&t);int k=1;while(t--){memset(tree,0,sizeof tree);scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);ad(i,x);}printf("Case %d:\n",k++);char a[10];while(~scanf("%s",a)){if(strcmp(a,"End")==0)break;if(a[0]=='Q'){int x,y;scanf("%d%d",&x,&y);printf("%d\n",getsum(y)-getsum(x-1));}else if(a[0]=='A'){int x,y;scanf("%d%d",&x,&y);ad(x,y);}else if(a[0]=='S'){int x,y;scanf("%d%d",&x,&y);ad(x,-y);}}}return 0;
}

这篇关于敌兵布阵 线段树（树状数组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---