学步园

题目链接:  http://poj.org/problem?id=3468

题目大意:  给出N个数，和M次查询

                 C a b c  区间[a,b]的值都加上c

                 Q a b     查询区间[a,b]值的和

解题思路:  线段树区间lazy延迟更新，每次插入区间标记lazy

                 下次再操作此区间时用lazy更新下面的子树

                  每个结点存储值是区间的和

                  更新和查询的时间复杂度都是O(logN)

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 201000
#define MID(a,b) (a+b)>>1
#define L(a) a<<1
#define R(a) (a<<1|1)
typedef struct{
    int left,right;
    long long int sum,add;
}Node;

Node Tree[MAX<<2]={0};
long long int num[MAX];

void Build(long long int t,int l,int r)             //以1为根节点建立线段树[l,r]
{
    Tree[t].left=l,Tree[t].right=r;
    if(Tree[t].left==Tree[t].right)
    {
        Tree[t].sum=num[Tree[t].right];
        Tree[t].add=0;
        return ;
    }
    int mid=MID(Tree[t].left,Tree[t].right);
    Build(L(t),l,mid);
    Build(R(t),mid+1,r);
    Tree[t].sum=Tree[L(t)].sum+Tree[R(t)].sum;
}

void Insert(long long int t,int l,int r,long long int m)   //向区间[l,r]插入m
{
    if(Tree[t].left==l&&Tree[t].right==r)
    {
        Tree[t].sum+=(Tree[t].right-Tree[t].left+1)*m;
        Tree[t].add+=m;
        return ;
    }
    if(Tree[t].add!=0)                   //无论是插入还是查询都要更新lazy
    {
        Tree[L(t)].sum+=(Tree[L(t)].right-Tree[L(t)].left+1)*Tree[t].add;
        Tree[R(t)].sum+=(Tree[R(t)].right-Tree[R(t)].left+1)*Tree[t].add;
        Tree[L(t)].add+=Tree[t].add;
        Tree[R(t)].add+=Tree[t].add;
        Tree[t].add=0;
    }
    int mid=MID(Tree[t].left,Tree[t].right);
    if(l>mid)
    {
        Insert(R(t),l,r,m);
    }
    else if(r<=mid)
    {
        Insert(L(t),l,r,m);
    }
    else
    {
        Insert(L(t),l,mid,m);
        Insert(R(t),mid+1,r,m);
    }
    Tree[t].sum=Tree[L(t)].sum+Tree[R(t)].sum;
}

long long int Query(long long int t,int l,int r)     //查询区间[a,b]
{
    if(Tree[t].left==l&&Tree[t].right==r)
    {
        return Tree[t].sum;
    }
    if(Tree[t].add!=0)                 //lazy更新
    {
        Tree[L(t)].sum+=(Tree[L(t)].right-Tree[L(t)].left+1)*Tree[t].add;
        Tree[R(t)].sum+=(Tree[R(t)].right-Tree[R(t)].left+1)*Tree[t].add;
        Tree[L(t)].add+=Tree[t].add;
        Tree[R(t)].add+=Tree[t].add;
        Tree[t].add=0;
    }
    int mid=MID(Tree[t].left,Tree[t].right);
    if(l>mid)
    {
        return Query(R(t),l,r);
    }
    else if(r<=mid)
    {
        return Query(L(t),l,r);
    }
    else
    {
        return Query(L(t),l,mid)+Query(R(t),mid+1,r);
    }
    Tree[t].sum=Tree[L(t)].sum+Tree[R(t)].sum;   //更新结点: 结点的值=左子树+右子树
}

int main()
{
    char ch;
    int n,a,b,c;
    long long int i,m;
    scanf("%d%lld",&n,&m);
    for(i=1;i<=n;i++)         //初始化输入
        scanf("%lld",&num[i]);
    Build(1,1,n);
    for(i=1;i<=m;i++)
    {
        getchar();
        scanf("%c",&ch);
        if(ch=='C')
        {
            scanf("%d%d%d",&a,&b,&c);
            Insert(1,a,b,c);            //区间[a,b]都加上c
        }
        else
        {
            scanf("%d%d",&a,&b);
            printf("%lld\n",Query(1,a,b));  //查询区间[a,b]的和
        }
    }
    return 0;
}

注：原创文章，转载请注明出处