线段树，从入门到入坑 - xyz的小窝 - 洛谷博客 (luogu.com.cn)

算法学习笔记(14): 线段树 - 知乎 (zhihu.com)

如何快速求出一个序列的区间和呢？可以使用前缀和。如何快速求出一个序列的最值呢？可 以使用 ST 表。这两种数据结构在建立的时候颇费功夫，但使用的时候效率很高。如果再增加一 个需求：时不时的修改序列的值，那么这两种数据结构就无法高效完成了。不过可以使用线段树 来解决这类问题。

在基础篇中，我们已经学习了二叉树的有关概念。而线段树是一种特殊的二叉树，它可以将 一个线性的序列组织成一个树状的结构，从而可以在对数的时间复杂度下访问序列上的任意一个 区间并进行维护。在本章中，将学习线段树的构建方法和一些简单的应用。

线段树，它将一段区间划分为若干 单位区间 ，每一个节点都储存着一个区间。它 功能强大 ，支持区间求和，区间最大值，区间修改，单点修改等操作。它的大致思想是：将一段大区间平均地划分成 2 22 个小区间，每一个小区间都再平均分成 2 22 个更小区间……以此类推，直到每一个区间的 L 等于 R （这样这个区间仅包含一个节点的信息，无法被划分）。通过对这些区间进行修改、查询，来实现对大区间的修改、查询。可以用线段树维护的问题必须满足 区间加法 ，否则是不可能将大问题划分成子问题来解决的。

例如：

符合区间加法的例子：

数字之和——总数字之和 = 左区间数字之和 + 右区间数字之和

最大公因数(GCD)——总GCD = gcd( 左区间GCD , 右区间GCD );

最大值——总最大值=max(左区间最大值，右区间最大值)

不符合区间加法的例子：

众数——只知道左右区间的众数，没法求总区间的众数

01序列的最长连续零——只知道左右区间的最长连续零，没法知道总的最长连续零

辨析：区间[L,R]指的是下标从L到R的这(R-L+1)个数，而不是指一条连续的线段。

线段树是将每个区间[L,R]分解成[L,M]和[M+1,R] (其中M=(L+R)/2 这里的除法是整数除法，即对结果下取整)

由于树的天然结构，线段树天生可以通过递归来逐步分解。

上图中，每个区间都是一个节点，每个节点存自己对应的区间的统计信息。

每层只有一个节点包含我们要修改的节点，因此每层只需要更新一个节点即可，复杂度是（logn)

使用懒标记后，对于那些正好是线段树节点的区间，我们不继续递归下去，而是打上一个懒标记，将来要用到它的子区间的时候，再向下传递。

更新时，我们是从最大的区间开始，递归向下处理。

它可以把懒标记下传。

设想一下，如果我们要把懒标记下传，应该注意什么呢？

首先，要给子节点打上懒标记。

然后，我们要修改子节点上的值。

最后，不要忘记把这个节点的懒标记清空。

详见代码

有了区间修改的经验，区间查询的方法完全类似。

接下来看模板罢

如题，已知一个数列，你需要进行下面两种操作：

第一行包含两个整数 $n, m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：

输出包含若干行整数，即为所有操作 2 的结果。

对于 $30\%$ 的数据：$n \le 8$，$m \le 10$。对于 $70\%$ 的数据：$n \le {10}^3$，$m \le {10}^4$。对于 $100\%$ 的数据：$1 \le n, m \le {10}^5$。

保证任意时刻数列中所有元素的绝对值之和 $\le {10}^{18}$。

【样例解释】