题解 P2068 【统计和】

~~把在a的位置上加上b看成变成b能过4组?黑人问号??~~ [宣传Blog](http://dedsecr.top/) 看楼下没人用zkw~~重口味~~线段树，特地来一发zkw线段树 *** 裸的线段树，具体看代码注释 ```cpp #include<iostream> #include<cstring> #include<cstdio> #include<string> #include<algorithm> #include<cmath> using namespace std; int n,m,M,tree[100001<<2]; void build(){for(M=1;M<=n+1;M<<=1);}//虽然不用建树，但求出M还是必要的 void change(int pos,int x) { tree[pos+=M]+=x;//修改叶子节点 for(pos>>=1;pos;pos>>=1)tree[pos]=tree[pos<<1]+tree[pos<<1|1];//从叶子节点向上返回 } int query(int l,int r) { int ans=0; for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1)//(l^r^1)==1时表示l和r不为兄弟 { if(~l&1)ans+=tree[l^1];//若l为左儿子 if(r&1)ans+=tree[r^1];//若r为右儿子 } return ans; } int main() { scanf("%d%d",&n,&m); build(); for(int i=1;i<=m;++i) { int x,y;char odd; cin>>odd; scanf("%d%d",&x,&y); if(odd=='x')change(x,y); else printf("%d\n",query(x,y)); } return 0; } ``` 关于zkw线段树的具体讲解请点[这里](https://zhuanlan.zhihu.com/p/29876526)