HDU1166 敌兵布阵 [线段树模板]

题意：在序列中修改单点和查询区间和

#include<iostream>

#include<cstdio>

#include<cstring>

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

using namespace std;

const int maxn=*;

int sum[maxn<<],add[maxn<<];//sum求和，add懒惰标记

int a[maxn]={},n=;//存原数组数据下标[1,n]

//更新节点信息，这里是求和

void pushup(int rt)

{

    sum[rt]=sum[rt<<]+sum[rt<<|];

}

//建树

void pushdown(int rt,int ln,int rn)

{//ln,rn为左子树，右子树的数量

    if(add[rt])//下推标记

    {

        add[rt<<]+=add[rt];

        add[rt<<|]+=add[rt];

        sum[rt<<]+=add[rt]*ln;

        sum[rt<<|]+=add[rt]*rn;

        add[rt]=;//清除本节点标记

    }

}

void build(int l,int r,int rt)//rt表示当前节点编号

{

    if(l==r)

    {

       sum[rt]=a[l];

       return;

    }

    int m=(l+r)>>;

    build(l,m,rt<<);

    build(m+,r,rt<<|);

    pushup(rt);

}

//点修改a[L]+=c;

//比如update(a,-b,1,n,1);//修改a点的值，减去b，当前节点区间是1到n，起始点是1

void update(int L,int c,int l,int r,int rt)

{//l,r当前节点区间，rt当前节点编号，L需要修改的节点，c修改的值

    if(l==r)

    {

        sum[rt]+=c;

        return;

    }

    int m=(l+r)>>;

    //根据条件判断调用左子树还是右子树

    if(L<=m)

        update(L,c,l,m,rt<<);

    else

        update(L,c,m+,r,rt<<|);

    pushup(rt);//子节点更新，所以本节点也需要更新

}

//区间修改a[r,t]+=c

////比如query(a,b,1,n,1))查询a b之间的和，当前节点区间是1到n，起始点是1

void update_(int L,int R,int c,int l,int r,int rt)

{//L,R表示操作区间，l,r表示当前节点区间，rt表示当前节点编号

    if(L<=l&&r<=R)//遍历的区间在操作区间内

    {

        sum[rt]+=c*(r-l+);

        add[rt]+=c;

        return;

    }

    int m=(l+r)>>;

    pushdown(rt,m-l+,r-m);

    if(L<=m)

        update_(L,R,c,l,m,rt<<);

    if(R>m)

        update_(L,R,c,m+,r,rt<<|);

    pushup(rt);

}

//区间查询 a[l,r]的和

//下推标记函数

int query(int L,int R,int l,int r,int rt)

{

    if(L<=l&&r<=R)

    {

        return sum[rt];

    }

    int m=(l+r)>>;

    pushdown(rt,m-l+,r-m);

    int ans=;

    if(L<=m)

        ans+=query(L,R,l,m,rt<<);

    if(R>m)

        ans+=query(L,R,m+,r,rt<<|);

    return ans;

}

int main()

{

    int t,cnt=;

    scanf("%d",&t);

    while(t--)

    {

        memset(a,,sizeof(a));

        memset(sum,,sizeof(sum));

        memset(add,,sizeof(add));

        scanf("%d",&n);

        for(int i=;i<=n;i++)

            scanf("%d",&a[i]);

        build(,n,);

        printf("Case %d:\n",cnt++);

        char str[];

        while(scanf("%s",str)&&str[]!='E')

        {

            int a,b;

            scanf("%d%d",&a,&b);

            if(str[]=='Q')

            {

                query(a,b,,n,);

            }

            if(str[]=='S')

                update(a,-b,,n,);//修改a点的值，减去b，当前节点区间是1到n，起始点是1

            if(str[]=='A')

                update(a,b,,n,);

            if(str[]=='Q')

                printf("%d\n",query(a,b,,n,));//查询a b之间的和，当前节点区间是1到n，起始点是1

        }

    }

    return ;

}