简介
zkw线段树虽然是线段树的另一种写法，但是本质上已经和普通的递归版线段树不一样了，是一种介于树状数组和线段树中间的存在，一些功能上的实现比树状数组多，而且比线段树好写且常数小。
普通线段树采用从上到下逐层递归的方式。zkw线段树则是从底层开始，目标直接明确，不需要线段树在确定区间的分治过程。
一些基础题
树状数组的题，据说模拟也能过hhhh。
单点修改，区间查询。各种数据结构都可搞，用最基本的zkw线段树实现。
//zkw segment tree
//by Cydiater
//2016.12.11
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <bitset>
#include <set>
#include <vector>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define FILE "shulie"
const int MAXN=1<<19;
const int LIM=1<<18;
const int M=1<<17;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,arr[MAXN],MM;
char s[15];
struct zkw_Segment_Tree{
int t[MAXN];
void build(){
up(i,M,LIM-1)t[i]=arr[i-M+1];
down(dep,16,0)up(i,1<<dep,(1<<(dep+1))-1)t[i]=t[i<<1]+t[i<<1|1];
}
int Query(int L,int R){
L-=1;R+=1;int ans=0;
for(int S=L+M,T=R+M;S^T^1;S>>=1,T>>=1){
if(~S&1) ans+=t[S^1];
if(T&1) ans+=t[T^1];
}
return ans;
}
void Change(int pos,int d){
for(pos+=M;pos;pos>>=1)t[pos]+=d;
}
}Tree;
namespace solution{
void Slove(){
N=read();
up(i,1,N)arr[i+1]=read();
Tree.build();
MM=read();
while(MM--){
scanf("%s",s);
if(s[0]=='S'){
int L=read(),R=read();
printf("%d\n",Tree.Query(L,R));
}
else{
int pos=read(),d=read();
Tree.Change(pos,d);
}
}
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
Slove();
return 0;
}