【HU 1166】敵兵布陣-単点修正と区間求和

タイトル:Nの長い数列Aで、これを操作します.1.Add/Sub i j:Aiを増加/減算します.2.Query i j:Ai++Ajの値を問い合わせる.問い合わせごとに正しい答えを出す.
作り方:入門問題は線分樹と樹状配列で全部できます.簡単です.
ツリー配列のプログラミングの複雑さが低いので、ここではツリー配列のコードだけを貼り付けます.

#include 
#include 
#include 
#include 
#include 
using namespace std;
int T,n,c[50010]={0};
char op[10]={0};

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

void add(int x,int a)
{
  for(int i=x;i<=n;i+=lowbit(i))
    c[i]+=a;
}

int sum(int x)
{
  int s=0;
  for(int i=x;i>0;i-=lowbit(i))
    s+=c[i];
  return s;
}

int query(int a,int b)
{
  return sum(b)-sum(a-1);
}

int main()
{
  scanf("%d",&T);
  for(int t=1;t<=T;t++)
  {
    scanf("%d
",&n);
	memset(c,0,sizeof(c));
	for(int i=1;i<=n;i++)
	{
	  int a;
	  scanf("%d",&a);
	  if (i==n) scanf("
");
	  add(i,a);
	}
	printf("Case %d:
",t);
	scanf("%s",op);
	while(op[0]!='E')
	{
	  int a,b;
	  scanf("%d %d
",&a,&b);
	  if (op[0]=='A') add(a,b);
	  if (op[0]=='S') add(a,-b);
	  if (op[0]=='Q') printf("%d
",query(a,b));
	  scanf("%s",op);
	}
  }
  
  return 0;
}