线段树整理

//每天整理一点，太多了 

https://www.cnblogs.com/TheRoadToTheGold/p/6254255.html#4175712（ORZ）

POJ  3468 板子题 注意下数据范围 （因为int会爆，以后一定好好看题，浪费我10min....）

http://poj.org/problem?id=3468

#include<iostream>//线段树题目集
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 4e5 + 15;
typedef long long ll;
typedef struct
{
    ll l,r,sum,f;//sum为区间和,f为懒人标记
}node;
node Tree[maxn];//线段树
ll n,q;
ll _left,_right,value;
void buildTree(int l,int r,int cur)
{
    Tree[cur].l = l;
    Tree[cur].r = r;//左右区间范围
    if(l==r)
    {
        scanf("%lld",&Tree[cur].sum);
        return;
    }
    int mid = (l + r) >> 1;
    buildTree(l,mid,cur*2);
    buildTree(mid+1,r,cur<<1|1);
    Tree[cur].sum = Tree[cur<<1].sum + Tree[cur<<1|1].sum; 
}//建树
void Down(int cur)
{
    Tree[2*cur].f += Tree[cur].f;
    Tree[2*cur+1].f += Tree[cur].f;
    Tree[2*cur].sum += (Tree[2*cur].r - Tree[2*cur].l + 1)*Tree[cur].f;
    Tree[2*cur+1].sum += (Tree[2*cur+1].r - Tree[2*cur+1].l + 1)*Tree[cur].f;
    Tree[cur].f = 0;//因为已经传下去了,所以清零
}//懒标记下传
ll ans;
void ask_interval(int cur)
{
    if(_left<=Tree[cur].l&&Tree[cur].r<=_right)
    {
        ans += Tree[cur].sum;
        return;
    }
    if(Tree[cur].f)
        Down(cur);//下传懒人标记
    ll mid = (Tree[cur].l + Tree[cur].r) >> 1;//mid 中间值
    if(_left<=mid)
        ask_interval(cur<<1);
    if(_right>mid)
        ask_interval(cur<<1|1);  
}
void change_interval(int cur)
{
    if(_left<=Tree[cur].l&&Tree[cur].r<=_right)//if node 在区间范围内
    {
        Tree[cur].sum += (Tree[cur].r - Tree[cur].l + 1)*value;
        Tree[cur].f += value;
        return;
    }
    if(Tree[cur].f)
        Down(cur);
    ll mid = (Tree[cur].l + Tree[cur].r) >> 1;//mid 中间值
    if(_left<=mid)
        change_interval(cur<<1);
    if(_right>mid)
        change_interval(cur<<1|1);
    Tree[cur].sum = Tree[cur<<1].sum + Tree[cur<<1|1].sum;//(important) 更新完后一定要更新sum的总和值  
}//线段树区间修改
int main()
{
    while(scanf("%lld%lld",&n,&q)==2)//写返回值,不然可能会有些很SB的output 超出limit
    {
        memset(Tree,0,sizeof(Tree));
        buildTree(1,n,1);//1 ~ n为范围,cur 为当前节点
        char cmd;
        while(q--)
        {
            ans = 0;
            getchar();
            scanf("%c",&cmd);//区间查询,区间修改
            scanf("%lld%lld",&_left,&_right);
            if(cmd==‘Q‘)
            {   
                ask_interval(1);
                cout<<ans<<endl;
            }else{
                scanf("%lld",&value);
                change_interval(1);
            }
        }
    }
}