Description
Lily 特别喜欢养花，但是由于她的花特别多，所以照料这些花就变得不太容易。她把她的花依次排成一行，每盆花都有一个美观值。如果Lily把某盆花照料的好的话，这盆花的美观值就会上升，如果照料的不好的话，这盆花的美观值就会下降。有时，Lily想知道某段连续的花的美观值之和是多少，但是，Lily的算术不是很好，你能快速地告诉她结果吗？
Input
第一行一个整数T，表示有T组测试数据。
每组测试数据的第一行为一个正整数N(N<=50000)，表示Lily有N盆花。接下来有N个正整数，第i个正整数ai表示第i盆花的初始美观值(1<=ai<=50)。
接下来每行有一条命令，命令有4种形式：
（1）Add i j, i和j为正整数，表示第i盆花被照料的好，美观值增加j(j<=30)
（2）Sub i j, i和j为正整数，表示第i盆花被照料的不好，美观值减少j(j<=30)
（3）Query i j, i和j为正整数，i<=j，表示询问第i盆花到第j盆花的美观值之和
（4）End，表示结束，这条命令在每组数据最后出现
每组数据的命令不超过40000条
Output
对于第i组数据，首先输出"Case i:"和回车。
对于每个"Query i j"命令，输出第i盆花到第j盆花的美观值之和。
Sample Input
Sample Output
#include "iostream"
#include "string.h"
using namespace std;
struct
{
int a,b;
int sum;
} t[140000];
int r[50010],SUM;
void buildtree(int i,int left,int right)
{
t[i].a=left;
t[i].b= right;
if(left==right)
{
t[i].sum=r[right];
}
else
{
buildtree (i<<1,left,(right+left)/2);
buildtree ((i<<1)+1,(right+left)/2+1,right);
t[i].sum=t[i<<1].sum+t[(i<<1)+1].sum;
}
}
void query(int i,int left ,int right)
{
if(left<=t[i].a&&right>=t[i].b)
SUM+=t[i].sum;
else
{
int min=(t[i].a+t[i].b)/2;
if(left>min) query ((i<<1)+1,left,right);
else if(right<=min) query (i<<1,left,right);
else
{
query (i<<1,left,right);
query ((i<<1)+1,left,right);
}
}
}
void add (int i,int left, int right)
{
t[i].sum+=right;
if(t[i].a==left&&t[i].b==left) return;
if(left>(t[i].a+t[i].b)/2) add((i<<1)+1,left,right);
else add (i<<1,left,right);
}
void sub (int i,int left, int right)
{
t[i].sum-=right;
if(t[i].a==left&&t[i].b==left) return ;
if(left>(t[i].a+t[i].b)/2) sub((i<<1)+1,left,right);
else sub (i<<1,left,right);
}
int main()
{
int n,m,i,j;
char command[10];
cin>>m;
j=0;
while(m--)
{
int temp,a,b;
cin>>n;
r[0]=0;
for(i=1;i<=n;i++)
cin>>r[i];
buildtree(1,1,n);
cout<<"Case "<<++j<<":"<<endl;
while(cin>>command)
{
if(strcmp(command,"End")==0)
break;
else if(strcmp(command,"Query")==0)
{
cin>>a>>b;
SUM=0;
query(1,a,b);
cout<<SUM<<endl;
}else if(strcmp(command,"Add")==0)
{
cin>>a>>b;
add(1,a,b);
}else if(strcmp(command,"Sub")==0)
{
cin>>a>>b;
sub(1,a,b);
}
}
}
return 0;
}
原文：http://www.cnblogs.com/llfj/p/5696998.html