线段树的板题，题意没什么好讲的吧。
区间求和，单点修改。
因为看主席树的时候看到那边的query是用迭代写的，因此想想来看看迭代的线段树。
其实关于单点修改和区间求和的部分，那张讲稿上已经讲得很清楚了，只是剩下一个怎么init线段树的问题。
其实仔细想一想应该也是能够写出来的，我就是按照他的思路然后自己写的......
init用的也是迭代的方法，假若不能理解的话，那还需再看看那个讲稿呀！
倒是打标记的地方没怎么看懂，可能是没写过线段树对应的题目的原因。
最后说关于效率的问题的话，以前写的普通线段树只用了390ms，用这个反倒是410ms+了。
反正哪个顺手写哪个吧，没有必要特意选择
讲稿：https://wenku.baidu.com/view/f27db60ee87101f69e319544.html
统计的力量，看了这个我或许还要去看看kd-tree?23333333
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int maxm=70010; int st[maxm*5],n,kcase=1,times,m,x,y,query(int le,int ri);; char str[20]; void init(),update(int node,int value); int main(){ ios_base::sync_with_stdio(0); cin>>times; while(times--){ cin>>n; init(); cout<<"Case "<<kcase++<<":\n"; while(cin>>str&&str[0]!='E'){ cin>>x>>y; if(str[0]=='Q') cout<<query(m+x-1,m+y+1)<<endl; else update(m+x,st[m+x]+(str[0]=='S'?-1:1)*y); } } return 0; } void init(){ m=n; while(m!=(m&-m))m-=m&-m; m<<=1; st[m]=0; for(int i=1;i<=n;++i) cin>>st[m+i]; memset(st+m+n+1,0,sizeof(int)*(m-n)); for(int i=m-1;i;--i) st[i]=st[i<<1]+st[i<<1|1]; } int query(int le, int ri){ int ans=0; while((le^ri)!=1){ if(!(le&1))ans+=st[le^1]; if(ri&1)ans+=st[ri^1]; le>>=1,ri>>=1; } return ans; } void update(int node,int value){ st[node]=value; while(node)node>>=1,st[node]=st[node<<1]+st[node<<1|1]; }
