首页 > 代码库 > hdu1166

hdu1166

没有用到懒惰标记的线段树问题,不过通过这道题找到了不用数组就能找到写update的方法了

#include<iostream>#include<queue>#include<algorithm>#include<cstring>#include<cstdio>using namespace std;#define max 50010#define INF 0x3f3f3f3fint tree[max*3],ans;void build(int rt,int L,int R){    if(L== R)    {        scanf("%d",&tree[rt]);    }    else    {        int M = (L+R)/2;        build(rt*2,L,M);        build(rt*2+1,M+1,R);        tree[rt]= tree[rt*2]+tree[rt*2+1];    }}void update(int rt,int L,int R,int p,int q){    if(L==R&&L == p)    {        tree[rt]+= q;    }    else    {        int M = (L+R)/2;        if (p<=M) update(rt*2,L,M,p,q);        else        update(rt*2+1,M+1,R,p,q);        tree[rt]= tree[rt*2]+tree[rt*2+1];    }}void query(int cur,int x,int y,int s,int t){    int mid = (x+y)>> 1,ls = cur<< 1,rs  =cur<<1|1;    if(x>= s&&y<= t)    {        ans += tree[cur];        return ;    }    //pushdown(cur,x,y);    if(mid>= s)      query(ls,x,mid,s,t);    if(mid+1<= t)      query(rs,mid+1,y,s,t);}int main(){    int n,a,b,c,count =0;scanf("%d",&n);    while(n--)    {        memset(tree,0,sizeof(tree));        ans =0;        count++;        scanf("%d",&a);        build(1,1,a);        char s[10];        printf("Case %d:\n",count);        while((scanf("%s",s)!= EOF)&&s[0]!=‘E‘)        {            ans =0;            scanf("%d%d",&b,&c);            if(s[0]==‘Q‘){query(1,1,a,b,c);printf("%d\n",ans);}            else if(s[0]==‘A‘){                update(1,1,a,b,c);            }            else update(1,1,a,b,-c);        }    }    return 0;}