线段树是一棵二叉搜索树，思想与分治很想，把一段区间平分平分再平分，平分到不能平分为止，可以进行方便的区间修改和区间查询，当然，树状数组能做的单点修改、单点查询，线段树也可以更好地实现，总之，线段树是树状数组的升级版，此外，线段树能做的平衡树也能做，但平衡树码量太大，考场上一般写不出来反正我是写不出来，就是会写也不会用，其次有些特殊的线段树如权值线段树也可以水过平衡树，可见，线段树的应用还是十分广泛的

(资料图)

一般的线段树都是递归建树，当然，也有一种不用递归建树的线段树，即非递归线段树——zkw 线段树当然，zkw 线段树并不是我们现在的主角，我们讲一下递归建树的操作首先，可以设置三个方便的宏定义偷懒

typedef long long ll;#define ls (p << 1)#define rs (p << 1 | 1)#define mid ((l + r) >> 1)// ls 左儿子 rs 右儿子 mid 中间值

因为线段树是棵二叉树，\(p\) 是当前节点的编号，所以一个结点的左儿子和右儿子可以表示为\(p \times 2\) 和 \(p \times 2 + 1\)，用位运算速度更快，但是要注意运算符之间的优先级，不熟悉的那就勤加括号吧反正加几个括号基本没影响，还不容易出错，不加白不加，至于这个 \(mid\)，纯粹是图省事刚才我们也讲了左右儿子的表示方法，所以我们的空间要开到原来的四倍，当然，线段树还有一种结构体存法，那个存法开两倍空间即可，但要维护的东西不少，所以也没剩多少空间，而且操作起来很麻烦，不如用这种左右儿子表示法来存储

ll val[N << 2];

如图，这是一颗线段树，每一个节点都代表着一个区间的信息，如 \(1\) 号节点代表着区间 \([1, 5]\)的和，\(4\) 代表着区间 \([1, 2]\) 的和，我们发现它是从中间值平分开的，这里就是分治的思想，二分，每部分在自己递归，最后再合并一下，上代码

void build(int p, int l, int r) {if (l == r) {val[p] = read();return ;}build(ls, l, mid);build(rs, mid + 1, r);pushup(p);}

代码也不是很长，宏定义是个好东西对于 pushup函数，你可能会想知道这是什么东西，别急，这就是接下来我们要讲的

更新函数，说白了就是将两个儿子的信息合并，合并的方式有多种，相加、相乘、取最值、dp 等等，具体题目具体分析，这里就展示一下相加类型的更新函数，要记住，建树和修改操作等一些操作，一定不要忘记更新！！！

void pushup(int p) {val[p] = val[ls] + val[rs];}

众所周知，线段树对于区间操作那可是十分厉害的，虽然树状数组也能实现区间操作，但是太麻烦，还要背公式，相对于线段树也不好理解，因此对于区间操作，一般都用线段树，还有一个东西叫分块，也是可以的当然并不是主角

还是刚刚的图修改区间 \([1 , 4]\)，在线段树上，\([4 , 4]\) 可以由 \([1, 4], [4, 4]\) 组成，在这里我们可以看出，当一段小区间属于这个修改的大区间时，我们可以直接对这个小区间进行操作，不必继续向下修改，但如果后面又对这个小区间中的更小的区间，如\([3, 3]\)进行修改，然后要查询它的值怎么办呢？这里我们要引入一个新的变量——\(lazy\)，俗称懒标记。线段树中的每一个元素都需要一个懒标记，所以它也要开到源数据的\(4\)倍

ll lazy[N << 2];

懒标记，由名得知，它很懒，为什么？因为它懒得继续向下一个一个元素修改，但判断这个区间全部属于要修改的大区间时，直接对着对当前节点进行标记，同时 \(lazy\) 负责记录对这个区间的操作，节省时间由此可以看出，懒也有懒的好处，它的含义是对当前节点的区间中所有的元素都进行一个操作，\(lazy\)也有很多类型，有的负责记录区间加减，有的负责记录区间乘除，还有负责乘方开方、是否异或等等，设置 \(lazy\) 的含义在一些题目当中也是一个难点，具体题目具体分析，在区间修改中，\(lazy\) 主要也是为了省时，这里以区间加减的修改函数为例

void change(int p, int l, int r, int lr, int rr, ll v) {if (lr <= l && r <= rr) {lazy[p] += v;val[p] += v * (r - l + 1);return ;}pushdown(p, l, r);if (lr <= mid) {change(ls, l, mid, lr, rr, v);}if (rr > mid) {change(rs, mid + 1, r, lr, rr, v);}pushup(p);}// l、r 当前节点所对应的区间 lr、rr 要修改的区间的左右边界 v 区间要加减的数

向下递归过程中，如果现在节点对应的区间 \([l, r]\) 已经被修改区间 \([lr, rr]\)包含，直接对当前节点进行操作，具体操作如代码所示，很好理解，不细说，\(lazy\) 加上 \(v\)，代表这段区间整体加上 \(v\)，如果有不属于\([lr, rr]\)的部分，分治，如果 \(lr\) 小于等于中间值，说明在当前对应区间的左半段有要进行修改操作的，向左孩子递归，\(rr\) 大于中间值，说明在当前对应区间的右半段也又要修改操作的，向右孩子递归，最后，不要忘记更新！，至于 pushdown操作，这就和我们的 \(lazy\) 有关了，我们存下 \(lazy\)，但是 \(lazy\) 到底在哪里有作用呢，这就引出了我们的

为了方便，我们一起将！区间查询这个操作，字面意思，就是个查询操作，但怎么查询才能更快呢，先上图假设，我们要查询区间[1, 5]的所有数的和，那我们只需要查询 \(1\) 号节点的数值就行了，\(1\) 号节点存储着区间 \([1, 5]\) 的和，所以，查询操作与修改操作有着一样的思路，遇到全属于大区间的小区间，直接返回小区间的值就行了但这里有个问题，假设我们已经对区间 \([1, 2]\) 都加上了 \(v\)，按照我们的修改操作，直接对 \(4\) 号节点进行更新，记录 \(lazy\)，那我现在要查询区间 \([1, 1]\)，即 \(8\) 号节点的信息怎么办，当初的修改操作压根就没递归到这一层，这时候，\(lazy\) 就派上用场了，还记得 \(lazy\) 的含义吗？对区间内所有的元素都进行一个操作，那么，我们是否可以把这个 \(lazy\) 下传给左右儿子呢？反正左右儿子都是属于这个区间的，这个修改也是对它们的修改，所以下传这个 \(lazy\) 没有什么影响，那我们就下传，这里就是加减操作的下传函数的代码。

void pushdown(int p, int l, int r) {if (!lazy[p])return ; // 没有lazy还下传个毛线lazy[ls] += lazy[p], val[ls] += lazy[p] * (mid - l + 1);lazy[rs] += lazy[p], val[rs] += lazy[p] * (r - mid);lazy[p] = 0; // 下传完了,它的lazy也就没了}

查询要下传，为什么修改也要下传呢？当然是因为修改函数中有 pushup函数，最后一更新，本来已经修改好的正确答案会被更新掉，如果下传了 \(lazy\)，那么更新后还是原来的正确答案，否则，最后会被错误答案代替，现在解决了 \(lazy\) 的问题，我们也就可以开心的进行区间查询了，上代码。

ll query(int p, int l, int r, int lr, int rr) {if (lr <= l && r <= rr) {return val[p];}pushdown(p, l, r);ll ans = 0;if (lr <= mid)ans += query(ls, l, mid, lr, rr);if (rr > mid)ans += query(rs, mid + 1, r, lr, rr);return ans;}

前面说了，树状数组能做的线段树都能做，那么树状数组的单点修改、单点查询在线段树上是 so easy 的，都是递归，没什么技术含量，只需 change函数的 \(lr, rr\) 都设成要修改的位置，就完成了，query函数是一样的，当然也可以自己再写个函数，下面给个例子

void update(int p, int l, int r, int x, ll v) {if (l == r) {val[p] += v;return ;}if (x <= mid) {update(ls, l, mid, x, v);}else update(rs, mid + 1, r, x, v);pushup(p);}ll query(int p, int l, int r, int x) {if (l == r) {return val[p];}if (x <= mid)return query(ls, l, mid, x);elsereturn query(rs, mid + 1, r, x);}

真的毫无技术含量

\(lazy\) 方面，有一种优化方法叫标记永久化标记永久化：如果确定懒惰标记不会在中途被加到溢出（即超过了该类型数据所能表示的最大范围），那么就可以将标记永久化。标记永久化可以避免下传懒惰标记，只需在进行询问时把标记的影响加到答案当中，从而降低程序常数。具体如何处理与题目特性相关，需结合题目来写。这也是树套树和可持久化数据结构中会用到的一种技巧。——\(\text{OI wiki}\)空间方面，有动态开点优化，可以与权值线段树搭配线段树方面，还有一些其他的线段树，如权值线段树、zkw 线段树。权值线段树，叶节点代表的不再是区间范围，而是权值，非叶节点代表的是权值区间而不是我们原本的区间，加上动态开点，可以水过洛谷的普通平衡树zkw线段树，先%为敬，非递归线段树，因为不递归，跑的是真的很快，但是不好理解，其次在竞赛中，初学者是真的不会用这个去做题，所以对像我这样的蒟蒻而言，也就拿它玩玩，水水模板，然后就吃灰了，这里给出洛谷普通线段树 \(1\) 的 zkw 线段树代码

#include using namespace std;typedef long long ll;const int N = 1e5 + 5;int n, num = 1, m;ll tree[N << 2], delta[N << 2];inline ll read() {ll x = 0;int fg = 0;char ch = getchar();while (ch < "0" || ch > "9") {fg |= (ch == "-");ch = getchar();}while (ch >= "0" && ch <= "9") {x = (x << 3) + (x << 1) + (ch ^ 48);ch = getchar();}return fg ? ~x + 1 : x;}void print(ll x, char y) {cout << x;putchar(y);}void build() {for (; num <= n + 1; num <<= 1);for (int i = num + 1; i <= num + n; ++ i) {tree[i] = read();}for (int i = num - 1; i >= 1; -- i) {tree[i] = tree[i << 1] + tree[i << 1 | 1];}}void change(int l, int r, ll v) {int lNum = 0, rNum = 0, nNum = 1;for (l = num + l - 1, r = num + r + 1; l ^ r ^ 1; l >>= 1, r >>= 1, nNum <<= 1) {tree[l] += v * lNum;tree[r] += v * rNum;if (~l & 1) {delta[l ^ 1] += v;tree[l ^ 1] += v * nNum;lNum += nNum;}if (r & 1) {delta[r ^ 1] += v;tree[r ^ 1] += v * nNum;rNum += nNum;}}for (; l; l >>= 1, r >>= 1) {tree[l] += v * lNum;tree[r] += v * rNum;}}ll query(int l, int r) {int lNum = 0, rNum = 0, nNum = 1;ll ans = 0;for (l = num + l - 1, r = num + r + 1; l ^ r ^ 1; l >>= 1, r >>= 1, nNum <<= 1) {if (delta[l]) {ans += delta[l] * lNum;}if (delta[r]) {ans += delta[r] * rNum;}if (~l & 1) {ans += tree[l ^ 1];lNum += nNum;}if (r & 1) {ans += tree[r ^ 1];rNum += nNum;}}for (; l; l >>= 1, r >>= 1) {ans += delta[l] * lNum;ans += delta[r] * rNum;}return ans;}int main() {n = read();m = read();build();for (int op, x, y, i = 1; i <= m; ++ i) {op = read(), x = read(), y = read();if (op == 1) {ll v = read();change(x, y, v);}else {print(query(x, y), "\n");}}return 0;}

其他方面的这些东西，有些很有用，有些也就图一乐，以后如果学会了，我会来补坑的。标记永久化：「学习笔记」线段树标记永久化可持久化线段树（权值线段树）：「学习笔记」可持久化线段树