HDU - 1166 敌兵布阵（树状数组模板题/线段树模板题）-白红宇

HDU - 1166 敌兵布阵（树状数组模板题/线段树模板题）

阅读量：2135 次

发布时间：2019-04-30

本文共 2195 字，大约阅读时间需要 7 分钟。

①树状数组

#include
   
    using namespace std;int n;int c[50010];int lowbit(int x){    return x & -x;}void add(int i,int val)// Add操作，将第i个元素增加val，那么他的父节点也要增加+{    while(i<=n)//注意判断这里不一定是n，这里应该是数值a[i]能达到的最大的值    {        c[i]+=val;        i+=lowbit(i);//i的父节点    }}int sum(int i){    int s=0;    while(i>0)    {        s+=c[i];        i-=lowbit(i);//I的前驱    }    return s;}int main(){    int T;    scanf("%d",&T);    int x,y;    for(int cas=1;cas<=T;++cas)    {        memset(c,0,sizeof(c));        printf("Case %d:\n",cas);        scanf("%d",&n);        for(int i=1;i<=n;++i)        {            scanf("%d",&x);            add(i,x);        }        char s[10];        while(scanf("%s",s))        {            if(s[0]=='E')                break;            scanf("%d%d",&x,&y);            if(s[0]=='A')                add(x,y);            else if(s[0]=='S')                add(x,-y);            else printf("%d\n",sum(y)-sum(x-1));//很像前缀和        }    }    return 0;}

②线段树

#include 
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          using namespace std;#define ll long long#define INF 1000000007int a[50010*4];inline void build(int root,int l,int r){ if(l==r) { scanf("%d",&a[root]); return ; } int mid=(l+r)>>1; build(root<<1,l,mid); build(root<<1|1,mid+1,r); a[root]=a[root<<1]+a[root<<1|1]; //a存的是总的区间和}inline void update(int x,int y,int root,int l,int r)//给编号为x的节点+y{ if(l==r) { a[root]+=y; return; } int mid=(l+r)>>1; if(x<=mid) update(x,y,root<<1,l,mid); else update(x,y,root<<1|1,mid+1,r); a[root]=a[root<<1]+a[root<<1|1];}inline int getsum(int x,int y,int root,int l,int r){ if(x<=l && r<=y) return a[root]; int mid=(l+r)>>1; int ans=0; if(x<=mid)//中间的mid点还是在左区间上 ans+=getsum(x,y,root<<1,l,mid); if(y>mid) ans+=getsum(x,y,root<<1|1,mid+1,r); return ans;}int main(){ //freopen("input.txt","r",stdin); int T,n; scanf("%d",&T); for(int cas=1;cas<=T;cas++) { scanf("%d",&n); printf("Case %d:\n",cas); build(1,1,n); char s[10]; while(~scanf("%s",s) && s[0]!='E') { int x,y; scanf("%d%d",&x,&y); if(s[0]=='A') update(x,y,1,1,n); else if(s[0]=='S') update(x,-y,1,1,n); else printf("%d\n",getsum(x,y,1,1,n)); } } return 0;}