描述
给定n个数据，有两个操作，加减其中的一个数据，当然还可查询在某段数据的和。
输入
输入数据有多组，每组数据的
第一行输入n，1=<n<=500000,代表数据的个数。
第二行输入具体数据，数据为正整数，范围在1到10000.
第三行输入m，1<=m<=100000,表示操作的次数。包含了修改和查询操作。
下面m行就是具体的操作了。
C i x 表示为第i个元素加上x，x范围在1到10000.
Q i j 表示查询区段i到j的和。保证输入的i<=j.
以EOF结束。
输出
输出查询后的区段和。
样例输入
8
1 5 9 11 2 8 15 6
4
Q 1 3
C 2 10
Q 1 4
Q 2 5
样例输出
15
36
37
泪目，终于会线段树了
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5e5+10,inf = 0x3f3f3f3f; int n,m; int a[N],sum[N * 4]; void build(int l,int r,int rt) { if(l == r) { sum[rt] = a[l];return; } int mid = (l + r) / 2; build(l,mid,rt * 2); build(mid + 1,r,rt * 2 + 1); sum[rt] = sum[rt*2] + sum[rt*2+1]; } void change(int k,int l,int r,int p,int v) //单点修改 在p的位置加上v { if(r < p || l > p)return ; if(l == r && l == p) { sum[k] += v; return ; } int mid = (l + r) / 2; change(k * 2 , l , mid , p , v); change(k * 2 + 1 , mid + 1 , r , p , v); sum[k] = sum[k * 2] + sum[k * 2 + 1]; //更新信息 } ll query(int k,int l,int r,int x,int y) //区间询问 询问x到y的区间和 { if(y < l || x > r)return 0; //[x,y]不在[l,r]中 if(l >= x && r <= y)return sum[k];//[x,y]在[l,r]中 int mid = (l + r) / 2; ll res = 0; res += query(k * 2,l,mid,x,y); res += query(k * 2 + 1,mid + 1,r,x,y); return res; } int main() { while(cin >> n) { //memset(sum,0,sizeof(sum)); for(int i = 1;i <= n; i++) { scanf("%d",&a[i]); } build(1,n,1);//构建线段树 cin >> m; char op; int l,r; while(m--) { getchar(); scanf("%c %d %d",&op,&l,&r); if(op=='C')change(1,1,n,l,r); else printf("%d\n",query(1,1,n,l,r)); } } return 0; }