描述：
假设有一列数{Ai}(1≤i≤n)，支持如下两种操作：
1.将Ak的值加d。（k, d是输入的数）
2.输出As+As+1+…+At。（s, t都是输入的数，s≤t）
输入：
第一行一个整数n，表示数列元素个数
第二行为n个整数，表示{Ai}的初始值。
第三行为一个整数m，表示操作数下接m行，每行描述一个操作，有如下两种情况：
ADD k d (表示将Ak加d，1<=k<=n，d为数)
SUM s t （表示输出As+…+At）
输出：
对于每一个SUM提问，输出结果
样例输入：
5
1 2 3 2 4
5
SUM 1 2
SUM 1 5
ADD 1 2
SUM 1 2
SUM 1 5
样例输出：
3
12
5
14
数据规模 m,n<=100000
#include <cstdio> #include <cstdlib> #include <iostream> #include <cstring> #include <string> #include <cmath> #include <algorithm> using namespace std; int n,m,k,d,s,t,a[100010],sum[100010]; int p=0; struct node { int a,b,left,right,v; }; node tree[400000]; void build(int x,int y) { p++; int now=p; tree[now].a=x; tree[now].b=y; tree[now].v=sum[y]-sum[x-1]; if(x<y) { tree[now].left=p+1; build(x,(x+y)/2); tree[now].right=p+1; build((x+y)/2+1,y); } } void add(int r) { tree[r].v=tree[r].v+d; if(tree[r].left!=0&&tree[tree[r].left].a<=k&&tree[tree[r].left].b>=k) add(tree[r].left); if(tree[r].right!=0&&tree[tree[r].right].a<=k&&tree[tree[r].right].b>=k) add(tree[r].right); } int getsum(int r) { int La,Lb,Ra,Rb; int tot=0; if(s<=tree[r].a&&tree[r].b<=t) return tree[r].v; else { La=tree[tree[r].left].a; Lb=tree[tree[r].left].b; if(!(La>t||Lb<s)) tot=tot+getsum(tree[r].left); Ra=tree[tree[r].right].a; Rb=tree[tree[r].right].b; if(!(Ra>t||Rb<s)) tot=tot+getsum(tree[r].right); return tot; } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; } build(1,n); scanf("%d",&m); while(m--) { char ch[10]; scanf("%s",ch); if(ch[0]=='A') { scanf("%d%d",&k,&d); add(1); } if(ch[0]=='S') { scanf("%d%d",&s,&t); printf("%d\n",getsum(1)); } } return 0; }