hdu 1166敌兵布阵(线段树也许树状数组)

hdu 1166敌兵布阵(线段树或者树状数组)

http://acm.hdu.edu.cn/showproblem.php?pid=1166

不懂得可以看刘汝佳训练指南P194

//线段树版：
#include <iostream>
#include <cstdio> 
#include <cstring>
using namespace std;
int n,s[50005*4];
void update(int id,int d,int L,int R,int O)
{
	int M=L+(R-L)/2;
	if(L==R) s[O]+=d;
	else
	{
		if(id<=M) update(id,d,L,M,O*2); else update(id,d,M+1,R,O*2+1);
		s[O]=s[O*2]+s[O*2+1];
	}
}
int query(int ql,int qr,int L,int R,int O)
{
	int M=L+(R-L)/2,ans=0;
	if(ql<=L&&R<=qr) return s[O];
	if(ql<=M) ans+=query(ql,qr,L,M,O*2);
	if(M<qr)  ans+=query(ql,qr,M+1,R,O*2+1);
	return ans;
}
int main(int argc, char *argv[])
{    int t,i,d,k=1; char a[10];
    scanf("%d",&t);
    while(t--!=0)
    {
        printf("Case %d:\n",k++);
            scanf("%d",&n);
            memset(s,0,sizeof(s));
            for(i=1;i<=n;i++)
            {
                scanf("%d",&d); update(i,d,1,n,1);
            }    
            while(scanf("%s",a))
            {
                if(a[0]=='E') break;
                scanf("%d%d",&i,&d);
                if(a[0]=='Q') printf("%d\n",query(i,d,1,n,1));
                else if(a[0]=='A') update(i,d,1,n,1);
                else if(a[0]=='S') update(i,-d,1,n,1);
            }
        }
    return 0;
}

//树状数组版：
#include <iostream>
#include <cstdio> 
#include <cstring>
using namespace std;
int n,s[50005];
int LowBit(int x)
{    return x&-x;  }
void Add(int x,int d)
{
    while(x<=n)
    {  s[x]+=d;  x+=LowBit(x);}
}
int Sum(int x)
{
    int ans=0;
    while(x>0)
    {    ans+=s[x];  x-=LowBit(x); }
    return ans;
}
int main(int argc, char *argv[])
{    int t,i,d,k=1; char a[10];
    scanf("%d",&t);
    while(t--!=0)
    {
        printf("Case %d:\n",k++);
            scanf("%d",&n);
            memset(s,0,sizeof(s));
            for(i=1;i<=n;i++)
            {
                scanf("%d",&d); Add(i,d);
            }    
            while(scanf("%s",a))
            {
                if(a[0]=='E') break;
                scanf("%d%d",&i,&d);
                if(a[0]=='Q') printf("%d\n",Sum(d)-Sum(i-1));
                else if(a[0]=='A') Add(i,d);
                else if(a[0]=='S') Add(i,-d);
            }
        }
    return 0;
}