线段树讲解（辅助理解）

题目大意：对一个序列进行区间修改和查询。
首先，如果想到只有区间查询或只有区间修改，我们可以想到使用树状数组进行求解。但是当前题目需要同时区间修改+查询，那么我们就需要一种新的数据结构：线段树

什么是线段树
即存储各个区间（线段）的二叉树

我们通过分治各个区间的左右子节点线段，将一个数组拆分成这样的线段数组：

即，对于一个节点U，它由它的左子节点U2，右子节点U2+1的和（这里只讨论维护和的情况）得到。

那么如果只是如此简单，那么时间复杂度有什么优化呢？

线段树的核心思想：懒标记
即，通过在父节点记录懒标记（需要增加/减少的值），直到某一区间（子节点）需要被查询，才下放懒标记至所有的子节点。
例如，我们分别在[1,8],[1,4],[1,2]区间的所有元素+1。所以上述区间的懒标记都加1，
即 lazy([1,8])+=1
lazy([1,4])+=1
lazy([1,2])+=1
仅在每次修改操作之后不进行所有子节点的修改操作

现在，当我查询区间[1,1] 的值时，上述区间所存储的懒标记都下放给它们的子节点。
于是，我们完成了线段树的操作。

首先，我们先定义一个结构体和线段树数组（一定要开4倍长度，否则会爆数组）

struct node{
    int l,r;
    ll sum,lazy;
}tree[4*maxn];

然后，我们根据上图及其思想，构建线段树

void build(int u,int l,int r){
    tree[u].l=l;
    tree[u].r=r;
    tree[u].lazy=0;
    if(l==r){
        tree[u].sum=a[l];
        return ;
    }
    int mid=l + (r - l) / 2;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    tree[u].sum=tree[u*2].sum+tree[u*2+1].sum;
}

接下来，就是其难点操作，释放懒标记

void pushdown(int u){
    if(tree[u].lazy!=0&&tree[u].l!=tree[u].r){//如果当前节点存在懒标记且不为叶子节点
        tree[u*2].sum+=tree[u].lazy*(tree[u*2].r-tree[u*2].l+1);
        tree[u*2].lazy+=tree[u].lazy;
        tree[u*2+1].sum+=tree[u].lazy*(tree[u*2+1].r-tree[u*2+1].l+1);
        tree[u*2+1].lazy+=tree[u].lazy;
        tree[u].lazy=0;//注意要清空懒标记
    }
 }

然后，我们可以进行区间增加操作：

void update(int u,int l,int r,ll val){
    if(tree[u].r<l||tree[u].l>r)return ;//如果当前递归到的区间不在目标区间中
    if(l<=tree[u].l&&tree[u].r<=r)//如果当前区间被完全包含，直接整个区间都加上val（目标增加值）并记录懒标记
        tree[u].sum+=val*(tree[u].r-tree[u].l+1);
        tree[u].lazy+=val;
        return ;
    }
//如果部分包含，需要先下放自身的懒标记，然后对其子节点递归操作
    pushdown(u);
    update(u*2,l,r,val);
    update(u*2+1,l,r,val);
    tree[u].sum=tree[u*2].sum+tree[u*2+1].sum;
}

最后进行区间查询操作，与上述的增值操作类似

ll query(int u,int l,int r){
    if(tree[u].r<l||tree[u].l>r)return 0;
    if(tree[u].l>=l&&tree[u].r<=r)return tree[u].sum;
    pushdown(u);
    return query(u*2,l,r)+query(u*2+1,l,r);
}

之后在主函数内进行操作注意：每次操作都是从1节点开始的

下面给出完整代码（进行结构体封装，这样可能会更方便但是也有可能会有玄学错误）

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
typedef long long ll;
typedef pair<int,int> pir;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define drep(i,a,b) for(int i=a;i>=b;i--)

struct SEG{
    struct node{
        int l,r;
        ll sum,lazy;
    }tree[4*maxn];
    ll a[maxn];
    void build(int u,int l,int r){
        tree[u].l=l;
        tree[u].r=r;
        tree[u].lazy=0;
        if(l==r){
            tree[u].sum=a[l];
            return ;
        }
        int mid=l + (r - l) / 2;
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
        tree[u].sum=tree[u*2].sum+tree[u*2+1].sum;
    }
    void pushdown(int u){
        if(tree[u].lazy!=0&&tree[u].l!=tree[u].r){
            tree[u*2].sum+=tree[u].lazy*(tree[u*2].r-tree[u*2].l+1);
            tree[u*2].lazy+=tree[u].lazy;
            tree[u*2+1].sum+=tree[u].lazy*(tree[u*2+1].r-tree[u*2+1].l+1);
            tree[u*2+1].lazy+=tree[u].lazy;
            tree[u].lazy=0;
        }
    }
    void update(int u,int l,int r,ll val){
        if(tree[u].r<l||tree[u].l>r)return ;
        if(l<=tree[u].l&&tree[u].r<=r){
            tree[u].sum+=val*(tree[u].r-tree[u].l+1);
            tree[u].lazy+=val;
            return ;
        }
        pushdown(u);
        update(u*2,l,r,val);
        update(u*2+1,l,r,val);
        tree[u].sum=tree[u*2].sum+tree[u*2+1].sum;
    }
    ll query(int u,int l,int r){
        if(tree[u].r<l||tree[u].l>r)return 0;
        if(tree[u].l>=l&&tree[u].r<=r)return tree[u].sum;
        pushdown(u);
        return query(u*2,l,r)+query(u*2+1,l,r);
    }
};
SEG seg;
int main(){
    int n,m;
    cin>>n>>m;
    rep(i,1,n) cin>>seg.a[i];
    seg.build(1,1,n);
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            int l,r,val;
            cin>>l>>r>>val;
            seg.update(1,l,r,val);
        }else{
            int l,r;
            cin>>l>>r;
            cout<<seg.query(1,l,r)<<'\n';
        }
    }
}