线段树水题刷刷，生活没有希望
最近看到代码跟树状数组差不多短的非递归线段树，常数也很小——zkw线段树
于是拿道水题练练手
短到让人身无可恋
void add(int pos,int x){ for(pos+=M+;pos;pos/=) a[pos]+=x;}
int que(int l,int r){ for(l+=M,r+=M+,ans=;l^r^;l>>=,r>>=)ans+=((l&)?:a[l|])+((r&)?a[r-]:);return ans;}
单点修改和区间查询（通过前缀和可以变成区间修改单点查询，再加特技标记可以变成区间修区间查）
M=;n+=;
while(M<n)
M*=;
M--;
for(int i=;i<=M+n+;i++)
a[i]=;
初始化（赋初值0是因为这道题多组数据，不然还不用）
#include <cstdio>
int t,n,M,p,l,r,ans,a[];char ch;
void add(int pos,int x){ for(pos+=M+;pos;pos/=) a[pos]+=x;}
int que(int l,int r){ for(l+=M,r+=M+,ans=;l^r^;l>>=,r>>=)ans+=((l&)?:a[l|])+((r&)?a[r-]:);return ans;}
int main()
{
scanf("%d",&t);
for(int T=;T<=t;T++)
{
printf("Case %d:\n",T);
scanf("%d",&n);
M=;n+=;
while(M<n)
M*=;
M--;
for(int i=;i<=M+n+;i++)
a[i]=;
for(int i=;i<=n;i++)
scanf("%d",&p),add(i,p);
for(ch=getchar();ch!='E' && ch!='Q' && ch!='A' && ch!='S';ch=getchar());
while(ch!='E')
{
switch(ch)
{
case'Q':
getchar();getchar();getchar();getchar();
scanf("%d%d",&l,&r);printf("%d\n",que(l,r));
break;
case 'A':
getchar();getchar();
scanf("%d%d",&l,&r);add(l,r);
break;
case 'S':
getchar();getchar();
scanf("%d%d",&l,&r);add(l,-r);
break;
}
for(ch=getchar();ch!='E' && ch!='Q' && ch!='A' && ch!='S';ch=getchar());
}
getchar();getchar();
}
return ;
}
这道水题理论上不需要常数那么小，但是代码短所以还是这么打了
主程序基本都是在输入输出，，，