全裸的单点更新....
代码：
#include#include #include using namespace std;#define MAXN 50002struct node{ int mid, l, r; int v;}a[MAXN*4]; // 4倍？int n;void pushUp(int e) { a[e].v = a[e<<1].v+a[e<<1|1].v; }void build(int l, int r, int e) //CALL: build(1, n, 1){ a[e].l=l, a[e].r=r; if(l==r) { scanf("%d", &a[e].v); } else { a[e].mid = (l+r)>>1; build(l, a[e].mid, e<<1); build(a[e].mid+1, r, e<<1|1); pushUp(e); //以前的做法是先init空的树，再insert数据。现在没有insert了。所以要pushUp }}void update(int p, int add, int l, int r, int e) //单点更新，CALL: update(p, add, 1, n, 1);{ if(l==r) { a[e].v+=add; } else { if(p<=a[e].mid) update(p, add, l, a[e].mid, e<<1); else update(p, add, a[e].mid+1, r, e<<1|1); pushUp(e); //以前的做法是，随着update，每个经过的区间都先add }}int query(int L, int R, int l, int r, int e) //查询[L, R]，CALL：query(L, R, 1, n, 1);{ int ret=0; if(L<=l && r<=R) //当前区间完全包含所查区间 { ret+=a[e].v; } else // l L R r { if(L<=a[e].mid) ret+=query(L, R, l, a[e].mid, e<<1); // L<= mid if(a[e].mid