题意：
给出一行数字，然后可以修改其中第i个数字，并且可以询问第i至第j个数字的和（i <= j）。
输入：
首行输入一个t，表示共有t组数据。
接下来每行首行输入一个整数n，表示共有n个数字。
接下来每行首先输入一个字符串，如果是”Add”，接下来是两个整数a，b，表示给第i个数增加b。如果是”Query”，接下来是两个整数a，b，表示查询从第i个数到第j个数之间的和。如果是”End”，表示这组数据结束。
输出：
每组数据首先输出”Case X: ”，其中X表示第x组数。
每次查询，输出计算结果，每个结果占一行。
题解：
点修改与区间求和，可以用树状数组模板。
具体见代码——
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std; const int N = ; int t, n;
int a[N];
int c[N];
char s[];
int x, y; int lowbit(int x)
{
return x&(-x);
} void Add(int x, int y)
{
a[x] += y;
while(x <= n)
{
c[x] += y;
x += lowbit(x);
}
} int Sum(int x)
{
int rt = ;
while(x > )
{
rt += c[x];
x -= lowbit(x);
}
return rt;
} int Summ(int l, int r)
{
int rt = ;
while(r >= l)
{
if(r-lowbit(r) < l)
{
rt += a[r];
r -= ;
}
else
{
rt += c[r];
r -= lowbit(r);
}
}
return rt;
} void Query(int a, int b)
{
printf("%d\n", Sum(b)-Sum(a-));
//printf("%d\n", Summ(a, b));
} int main()
{
//freopen("test.in", "r", stdin);
scanf("%d", &t);
for(int tm = ; tm <= t; tm++)
{
scanf("%d", &n);
memset(c, , sizeof(c));
memset(a, , sizeof(a));
int y;
for(int i = ; i <= n; i++)
{
scanf("%d", &y);
Add(i, y);
}
printf("Case %d:\n", tm); scanf("%s", s);
while(s[] != 'E')
{
scanf("%d%d", &x, &y);
if(s[] == 'A') Add(x, y);
if(s[] == 'Q') Query(x, y);
if(s[] == 'S') Add(x, -y);
scanf("%s", s);
}
}
}
树状数组区间求和模板——