写在前面

线段树是一种特别玄学的数据结构，它可以维护（优化）一些线段（区间）的算法，使其的时间复杂度由$\Theta(n)$变成$\Theta(\log n)$，无疑是一种完美的优化。

线段树长啥样？

大概长这样：

解释一下这个图：
$l,r$表示这个节点所对应的区间，比如节点1所对应的区间为$[1,4]$，上面的数字代表着节点编号。

线段树的几个性质

仔细观察上图得：
1：左孩子的编号为父亲的两倍

写出代码：

int lchild(int root) {  //root代表父亲节点
    return root * 2;  //返回左孩子的节点
}

2:右孩子的编号为父亲的两倍加一

代码：

int rchild(int root) {  //root代表父亲节点
    return root * 2 + 1;  //返回右孩子的节点
}

上面两条性质我们可以推广到任意的完全二叉树，接下来是线段树独有的特性
3：:左孩子管理的区间是$[l,\frac{l + r}{2}]$（$l,r$表示父亲管理的区间的左边界和右边界）
4：右孩子管理的区间是$[\frac{l + r}{2} + 1,r]$
5:父亲节点的的权值由子节点取得

例题分析

【模板】线段树 1

首先我们先把样例搞下来：

（快把我画死了）
我们发现这里多了一个$pre$，这是干嘛用的？
其实，$pre$表示的就是$[l,r]$的区间和，也就是该节点的权值。
那我们开始构建我们的线段树吧！！

第一步，存下这个线段树：

namespace SegmentTree {
    struct Seg {
        int l,r;
        long long lazy;
        long long pre;
    };

    Seg Tree[N * 4];

    int lchild(int root) {
        return root * 2;
    }
    int rchild(int root) {
        return root * 2 + 1;
    }
};  

那个$lazy$先不去管它，后面有用。
其实线段树不需要开四倍空间，三倍就够了，确切的说是$2\times n + 1$，不过不要这么小气。

第二步，建树（build操作）

这个怎么做呢？
1：确定每个节点控制的区间范围，这个很简单对吧？
2：确定每一个节点的值，这个我们分类讨论。如果它是一个叶子节点，那么它的权值就是他控制的端点$a[l]$；如果它不是子节点，那么它的值由它的两个子节点的权值确定。
没了。

建树操作$code$

void build(int root,int l,int r) {
    Tree[root].l = l;  //确定左右端点
    Tree[root].r = r;
    if(l == r) {  //如果它是叶子节点
        Tree[root].pre = a[l];  //控制的就是a[l]
        return;  //注意return
    }
    int mid = (l + r) >> 1;  //取中，同性质
    build(lchild(root),l,mid);  //继续构造两个儿子
    build(rchild(root),mid + 1,r);
    Tree[root].pre = Tree[lchild(root)].pre + Tree[rchild(root)].pre;  //父节点的值由子节点确定
}  

这一步必须好好理解，不然后面的区间修改和查询你就看不懂了。

第三步，区间修改（update操作）

这个比建树难很多，那个$lazy$有什么用你们马上就要知道了。
这个我们用图来感性理解一下：

其中蓝色表示线段树节点控制的范围，红色表示我们要找的范围。
在这种情况下，节点控制的所有数是不是都要改？包括它的孩子也要做改动？
但是我们在这里不管这么多，改动孩子我们交给懒标记 lazy 就好了， lazy 我们过一下讲。再看这张图：

这个怎么办？
很明显，我们需要改动的只有蓝l到红r的数，这个我们让孩子来做。

好了，我们开始讲 lazy

正如之间所说，它是一个懒标记，每次我们改动了一个节点的数时，就写一句：

Tree[root].lazy += k;

完了，剩下来的是让孩子去做吧。
怎么让孩子做呢？
我们写一个 push_down 函数，这个我们跟着代码来理解。

void push_down(int root) {  //传入父节点编号
    if(Tree[root].lazy) {
        Tree[lchild(root)].pre += Tree[root].lazy * (Tree[lchild(root)].r - Tree[lchild(root)].l + 1);  //下传懒标记，父亲懒标记里加的东西儿子都没有加过
        Tree[rchild(root)].pre += Tree[root].lazy * (Tree[rchild(root)].r - Tree[rchild(root)].l + 1);
        Tree[lchild(root)].lazy += Tree[root].lazy;  //两个孩子传了懒标记，现在继续下传
        Tree[rchild(root)].lazy += Tree[root].lazy;
        Tree[root].lazy = 0;  //父亲不欠左右孩子了，懒标记清0
    }
}

这样就好理解了吧！
理解了之后，我们就可以继续讲 update 了，我们分情况来讨论。
1.给定现结点的左右区间记为$[l,r]$，我们要找的区间记为$[L,R]$，若$[l,r] \subseteq [L,R]$，那么$[l,r]$全加
2.如果$[l,\frac{l+r}{2}] \subseteq [L,R]$，让左孩子操作
3.如果$[\frac{l+r}{2} + 1,r] \subseteq [L,R]$，让右孩子操作
放代码

void update(int root,int l,int r,int k) {
    if(Tree[root].l >= l && Tree[root].r <= r) {
        Tree[root].pre += (long long)k * (Tree[root].r - Tree[root].l + 1);
        Tree[root].lazy += k;
        return;
    }
    push_down(root);
    int mid = (Tree[root].l + Tree[root].r) >> 1;
    if(l <= mid) update(lchild(root),l,r,k);
    if(r > mid) update(rchild(root),l,r,k);
    Tree[root].pre = Tree[lchild(root)].pre + Tree[rchild(root)].pre;
}

还行吧，感受到算法的奇妙了吗？
好好理解，重点是如何传 lazy 和控制区间。

第四步，区间求和（query 操作）

接下来我们讲 query，讲完了我们这道题就做完了。
其实 query 和 update 差不了多少，看下面：
1. 若该线段树所控制的区间在目标区间内，则直接加上控制的这个值
2. 在左边或者右边的话同 update 操作
最后定义一个 ans 记录和就好了！！

放代码

long long query(int root,int l,int r) {
    if(Tree[root].l >= l && Tree[root].r <= r) return Tree[root].pre;
    push_down(root);
    int mid = (Tree[root].l + Tree[root].r) >> 1;
    long long cnt = 0;
    if(l <= mid) cnt += query(lchild(root),l,r);
    if(r > mid) cnt += query(rchild(root),l,r);
    return cnt;
}

所以我们就做完了线段树的模板1,放代码！！

#include <bits/stdc++.h>
using namespace std;

namespace IO {
    #pragma GCC target("avx")
    #pragma GCC optimize("Og")
    #pragma GCC optimize("Ofast")

    template<class T>
    inline void read(T& x) {
        x = 0;
        int p = 1;
        char ch = getchar();
        while(ch < '0' || ch > '9') {
            if(ch == '-') p = -1;
            ch = getchar();
        }
        while(ch >= '0' && ch <= '9') {
            x = x * 10 + ch - '0';
            ch = getchar();
        }
        x = x * p;
    }

    template<class T>
    inline void write(T x) {
        if(x < 0) {
            x = -x;
        }
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
};

using namespace IO;

const int N = 100010;

int a[N];
int n,q;

namespace SegmentTree {  //线段树
    struct Seg {
        int l,r;
        long long lazy;
        long long pre;
    };

    Seg Tree[N * 4];

    int lchild(int root) {
        return root * 2;
    }
    int rchild(int root) {
        return root * 2 + 1;
    }

    void build(int root,int l,int r) {
        Tree[root].l = l;
        Tree[root].r = r;
        if(l == r) {
            Tree[root].pre = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(lchild(root),l,mid);
        build(rchild(root),mid + 1,r);
        Tree[root].pre = Tree[lchild(root)].pre + Tree[rchild(root)].pre;
    }

    void push_down(int root) {
        if(Tree[root].lazy) {
            Tree[lchild(root)].pre += Tree[root].lazy * (Tree[lchild(root)].r - Tree[lchild(root)].l + 1);
            Tree[rchild(root)].pre += Tree[root].lazy * (Tree[rchild(root)].r - Tree[rchild(root)].l + 1);
            Tree[lchild(root)].lazy += Tree[root].lazy;
            Tree[rchild(root)].lazy += Tree[root].lazy;
            Tree[root].lazy = 0;
        }
    }

    void update(int root,int l,int r,int k) {
        if(Tree[root].l >= l && Tree[root].r <= r) {
            Tree[root].pre += (long long)k * (Tree[root].r - Tree[root].l + 1);
            Tree[root].lazy += k;
            return;
        }
        push_down(root);
        int mid = (Tree[root].l + Tree[root].r) >> 1;
        if(l <= mid) update(lchild(root),l,r,k);
        if(r > mid) update(rchild(root),l,r,k);
        Tree[root].pre = Tree[lchild(root)].pre + Tree[rchild(root)].pre;
    }

    long long query(int root,int l,int r) {
        if(Tree[root].l >= l && Tree[root].r <= r) return Tree[root].pre;
        push_down(root);
        int mid = (Tree[root].l + Tree[root].r) >> 1;
        long long cnt = 0;
        if(l <= mid) cnt += query(lchild(root),l,r);
        if(r > mid) cnt += query(rchild(root),l,r);
        return cnt;
    }
};

using namespace SegmentTree;  //使用这个namespace

int main() {
    read(n);read(q);
    for(int i = 1;i <= n;i++) {
        read(a[i]);
    }
    build(1,1,n);
    for(int i = 1;i <= q;i++) {
        int opt;
        read(opt);
        if(opt == 1) {
            int l,r,k;
            read(l);read(r);read(k);
            update(1,l,r,k);
        }else {
            int l,r;
            read(l);read(r);
            write(query(1,l,r));puts("");
        }
    }
    return 0;
}