#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

struct seg{
	int l;
	int r;
	int n;
}t[150011];


void build(int l,int r,int k)
{
	int mid;
	if(l==r)
	{
		t[k].l=l;
		t[k].r=r;
		t[k].n=0;
		return;
	}
	mid=(l+r)/2;
	t[k].l=l;
	t[k].r=r;
	t[k].n=0;
	build(l,mid,k+k);
	build(mid+1,r,2*k+1);
}

void insert(int n,int d,int k)
{
	int mid;
	if(t[k].l==t[k].r&&t[k].l==d)
	{
		t[k].n+=n;
		return;
	}
	mid=(t[k].l+t[k].r)>>1;
	if(d<=mid)
	insert(n,d,2*k);
	else
	insert(n,d,2*k+1);
	t[k].n=t[2*k].n+t[2*k+1].n;
}

int ans;
void search(int l,int r,int k)
{
	int mid;
	if(t[k].l==l&&t[k].r==r)
	{
		ans+=t[k].n;
		return;
	}
	mid=(t[k].l+t[k].r)>>1;
	if(r<=mid)
	search(l,r,2*k);
	else if(l>mid)
	search(l,r,2*k+1);
	else{
		search(l,mid,2*k);
		search(mid+1,r,2*k+1);
	}
}

int main()
{
	int T;
	int n,i,j,k,temp;
	char str[11];
	int a,b;
	j=0;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		build(1,n,1);
		for(i=1;i<=n;i++)
		{
			scanf("%d",&temp);
			insert(temp,i,1);
		}
		printf("Case %d:n",++j);
		while(scanf("%s",str),strcmp(str,"End"))
		{
			scanf("%d%d",&a,&b);
			if(strcmp(str,"Add")==0)
			insert(b,a,1);
			else if(strcmp(str,"Sub")==0)
			insert(-b,a,1);
			else
			{
				ans=0;
				search(a,b,1);
				printf("%dn",ans);
			}
		}
	}
	return 0;
}

分析：

刚在别人的博客上看到用树状数组写这道题，感觉很牛逼，其中记录数据的方式很方便。

代码：

<pre class="cpp" name="code">#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

int n,a[50005];
char tr[15];

int lowbit(int i)
{
	return i&(-i);
}

void update(int val,int i)
{
	while(i<=n)
	{
		a[i]+=val;
		i+=lowbit(i);
	}
}

int sum(int i)
{
	int sum=0;
	while(i>0)
	{
		sum+=a[i];
		i-=lowbit(i);
	}
	return sum;
}

int main()
{
	int i,val,t,x,y,zz=1;
	scanf("%d",&t);
	while(t--)
	{
		memset(a,0,sizeof(a));
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		{
			scanf("%d",&val);
			update(val,i);
		}
		printf("Case %d:n",zz++);
		while(scanf("%s",tr))
		{
			if(tr[0]=='E')
			break;
			scanf("%d%d",&x,&y);
			if(tr[0]=='A')
			update(y,x);
			else if(tr[0]=='S')
			update(-y,x);
			else
			printf("%dn",sum(y)-sum(x-1));
		}
	}
	return 0;
} 

敌兵布阵

      
      

       
       1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End 
      
      

      
      

       
       Case 1:
6
33
      
      
      
      

       
       59
      
      
      
      

       
       代码：