[C++知识库]线段树模板（1）

题解：记得开long long，没啥。
区间更新那一块的递归调用，不断下放，刚开始挺难理解的，也还好。

啊啊，松懈了好多，都怪自己被一部好看的小说引诱了……明天陪发小再玩一趟，赶紧回到正轨上，抓紧学习算法，不能玩物丧志！！！！
人要堕落是很容易的！！况且我想做到的事情还很多呢

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
int a[maxn],n,m;
struct node
{
    int val,lazy;
}sg[maxn<<2];
void pushup(int rt)
{
    sg[rt].val=sg[rt<<1].val+sg[rt<<1|1].val;
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        sg[rt].val=a[l];return ;
    }
    sg[rt].lazy=0;
    int m=(l+r)/2;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    pushup(rt);
}
void pushdown(int rt,int ln,int rn)
{
    if(sg[rt].lazy)
    {
        sg[rt<<1].lazy+=sg[rt].lazy;
        sg[rt<<1|1].lazy+=sg[rt].lazy;
        sg[rt<<1].val+=sg[rt].lazy*ln;
        sg[rt<<1|1].val+=sg[rt].lazy*rn;
        sg[rt].lazy=0;
    }
}
void update(int L,int R,int C,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        sg[rt].val+=C*(r-l+1);
        sg[rt].lazy+=C;
        return;
    }
    int m=(l+r)>>1;
    pushdown(rt,m-l+1,r-m);
    if(L<=m) update(L,R,C,l,m,rt<<1);
    if(R>m)  update(L,R,C,m+1,r,rt<<1|1);
    pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)
        return sg[rt].val;
    if(L>r||R<l)
        return 0;
    int m=(l+r)/2;
    pushdown(rt,m-l+1,r-m);
    return query(L,R,l,m,rt<<1)+query(L,R,m+1,r,rt<<1|1);
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,n,1);
    while(m--)
    {
        //memset()
        int g;scanf("%lld",&g);
        if(g==1)
        {
            int x,y,k;scanf("%lld%lld%lld",&x,&y,&k);
            update(x,y,k,1,n,1);
        }
        else if(g==2)
        {
            int x,y;scanf("%lld%lld",&x,&y);
            cout<<query(x,y,1,n,1)<<endl;
        }
    }
    return 0;
}