竹子听

4月7日晚修 -- ZKW线段树

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define maxn 10000

int M,n,m,tree[maxn],temp;

int LetMeAsk(int x){int i=1;while(1){i=i<<1;if(i>=x)return i;}}

void build(int t)

{

M=LetMeAsk(n);

for(int i=M;i<=M+n;i++)  scanf("%d",&tree[i]);//这里要注意开头的点序号就是M而不是M+1

}

void updata()

{

for(int i=M-1;i>=1;i--) tree[i]=tree[i<<1]+tree[i<<1|1];//奇妙的位运算 

}

void printff()

{

for(int i=M;i<M+n;i++) printf("%d ",tree[i]);//这里是小于而不是小于等于 

printf("\n");

}

void change(int x,int y)

{

int t=(M+x-1)>>1;

tree[M+x-1]=y;

while(t)

{

tree[t]=tree[t<<1]+tree[t<<1|1];

t=t>>1;

}

printff();

}

int query(int x,int y)

{

int ans=0;

x=M+x-2,y=M+y;//这里记得要加上一个M啊 

while(1)

{

if(x%2==0) ans+=tree[x+1];

if(y%2==1) ans+=tree[y-1];

x>>=1,y>>=1;

if(x+1==y) break;

}

printf("%d\n",ans);

}

int main()

{

int t,x,y;

char c;

memset(tree,0,sizeof(int));

scanf("%d%d\n",&n,&m);

build(M);

updata();

for(int i=1;i<=m;i++)

{

scanf("\n%c %d%d",&c,&x,&y);

if(c=='c')

change(x,y);//把x号节点的值改成y 

if(c=='q')

query(x,y);

}

}