线段树点和

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; const int maxn=1e5+10; int sto[maxn<<2]; void pushup(int rt) { sto[rt]=sto[rt<<1]+sto[rt<<1|1]; } void build(int l,int r,int rt) { if(l==r) { scanf("%d",&sto[rt]); return ; } int mid=(l+r)>>1; build(lson); build(rson); pushup(rt); } void update(int p,int v,int l,int r,int rt) { if(l==r) { sto[rt]=v; return; } int mid=(r+l)>>1; if(p<=mid) update(p,v,lson); else update(p,v,rson); pushup(rt); } int query(int L,int R,int l,int r,int rt) { if(L>=l&&R<=r) return sto[rt]; int mid=(r+l)>>1; int sum=0; if(L<=mid) sum+=query(L,R,lson); if(mid<R) sum+=query(L,R,rson); return sum; } int main() { int n, q; while(scanf("%d%d", &n, &q) != EOF) { build(1, n, 1); while(q--) { char str[5]; scanf("%s", str); if(str[0] == 'Q') { int l, r; scanf("%d%d", &l, &r); printf("%d\n", query(l, r, 1, n, 1)); } else { int pos, value; scanf("%d%d", &pos, &value); update(pos, value, 1, n, 1); } } return 0; } }