POJ 3468 A Simple Problem with Integers 线段树 （成段更新）

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

题意：给你若干点，成段的增加和询问。

思路：最基础的线段树成段更新模板题，LAZY-SET的应用。一句话就是：“更到你时就停住，用到你时候向下更”。自己写的比较挫，网上的代码写的十分飘逸，当个模板基础用，以后完善。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 100005
#define INF 1<<25
#define MAX 0x7fffffff
typedef long long ll;
using namespace std;
struct Line
{
    int left,right;
    ll value,add;
}line[maxn*4];
void build_tree(int l,int r,int step)
{
    line[step].left=l;
    line[step].right=r;
    line[step].add=0;
    if(l==r)
    {
        scanf("%lld",&line[step].value);
        return ;
    }
    int mid=(l+r)/2;
    build_tree(l,mid,step<<1);
    build_tree(mid+1,r,step<<1|1);
    line[step].value=line[step<<1].value+line[step<<1|1].value;
}
void downward(int step,int m)
{
    if(line[step].add)
    {
          line[step<<1].add+=line[step].add;
        line[step<<1|1].add+=line[step].add;
          line[step<<1].value+=line[step].add*(m-m/2);
        line[step<<1|1].value+=line[step].add*(m/2);
        line[step].add=0;
    }
}
void update(int l,int r,int step,int t)
{
    if(line[step].left==l&&line[step].right==r)
    {
        line[step].add+=t;
        line[step].value+=(ll)t*(r-l+1);
        return ;
    }
    if(line[step].left==line[step].right)
    return ;
        downward(step,line[step].right-line[step].left+1);
    int mid=(line[step].left+line[step].right)>>1;
    if(r<=mid)
    update(l,r,step<<1,t);
    else if(l>mid)
    update(l,r,step<<1|1,t);
    else
    {
        update(l,mid,step<<1,t);
        update(mid+1,r,step<<1|1,t);
    }
    line[step].value=line[step<<1].value+line[step<<1|1].value;
}
ll query(int l,int r,int step)
{
    if(l==line[step].left&&r==line[step].right)
    return line[step].value;
    downward(step,line[step].right-line[step].left+1);
    int mid=(line[step].left+line[step].right)>>1;
    ll ans=0;
    if(r<=mid)
    return query(l,r,step<<1);
    else if(l>mid)
    return query(l,r,step<<1|1);
    else
    {
        return query(l,mid,step<<1)+query(mid+1,r,step<<1|1);
    }
    return ans;
}
int main()
{
    int t_point,t_query,x,y;
    char ss[2];
    int t;
    scanf("%d%d",&t_point,&t_query);
    build_tree(1,t_point,1);
    for(int ii=0;ii<t_query;ii++)
    {
        scanf("%s",ss);
        if(ss[0]==‘Q‘)
        {
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(x,y,1));
        }
        else if(ss[0]==‘C‘)
        {
            scanf("%d%d%d",&x,&y,&t);
            update(x,y,1,t);
        }
    }
}

原文：http://blog.csdn.net/ooooooooe/article/details/19573873