OI：线段树

线段树简介

线段树是一种数据结构，在 $O(\log n)$ 的时间复杂度下支持单点修改单点查询、单点修改区间查询、区间修改单点查询甚至区间修改区间查询。虽然相较于树状数组常数较大，但是应用范围更广。

线段树实现过程

线段树基本思路

这里以 P3372【模板】线段树 1 为例。采用分治思想，我们如果想要维护出整个序列中任意一个区间的和，就要先维护出前半段的区间的和以及后半段的区间的和。想要维护出这两个区间中的和也采用同样的方法。最终我们可以建成一棵线段树。

我们惊喜的发现任何一个区间都能由上图中的区间拼接而成，而且任意一个区间都可以用不超过 $2\log n$ 个区间表示，所以我们考虑维护所有上图区间的和（这里用该题样例做演示）.

例如如果我们要查询 $2\sim 5$ 这一段区间的和，我们就可以用深度优先搜索找到 $3$ 个区间 $2\sim 2$，$3\sim 3$ 以及 $4\sim 5$，然后把这 $3$ 段的和加起来就是最终的答案。时间复杂度 O(log⁡n)。

修改时考虑把所有包含需要修改的区间的和全部修改，虽然这个方法在单点修改时速度较快，但是如果是区间修改，就会退化成 $O(n)$，考虑优化。

线段树懒标记

由于前面的方法复杂度瓶颈在于修改，考虑到前面询问只需要对 2log⁡n个区间进行累加求和，那么修改能否只修改这些区间呢？这显然是不行的，但是我们可以先把这些区间修改了，其他的打上标记，等到询问这些区间的时候再更新。

这样在修改时时间复杂度变为 $O(\log n)$，询问时时间复杂度依旧为 $O(\log n)$，总时间复杂度 $O(q\log n)$。线段树常数相较于树状数组较大，因此可以使用树状数组时尽量要写树状数组。

线段树具体实现

参考 https://oi-wiki.org/ds/seg/，写的太丑就先不放代码了。

线段树应用

基础应用

P3373 线段树 2

该题相较于 P3372【模板】线段树 1 多了区间乘操作，增加一个乘标记即可，需要注意的是下传标记时要先下传乘标记再下传加标记即可。

P4513 小白逛公园

该题需要维护 $4$ 个变量：区间和，最大字段和，以及区间包含左端点、包含右端点的最大字段和。上传下传都较为简单，可以参考题解。

均摊思想

线段树往往不会单独考察，有些题目需要我们观察性质，可能一个操作最坏情况下需要花费很多时间，但是所有操作总共反而不需要花费很多时间。

P4145 上帝造题的七分钟 2 / 花神游历各国

这题乍一看不好做，因为开根操作求加和直接用线段树是做不了的。但是一个数如果做开根操作，我们发现它最多会进行 $O(\log \log V)$ 次变成 $1$，其中 $V$ 取 10121012。因此我们用并查集维护出每一个位置的下一个非 $1$ 位置，然后我们快速找出修改区间中所有非 $1$ 的数，用线段树进行单点修改即可。

P9989 [Ynoi Easy Round 2023] TEST_69

这题虽然是 Ynoi 的题，但是实际上很好做，考虑到 gcd⁡(a,x)≠agcd(a,x)=a 时，$\gcd (a,x)$ 此时必然不超过 a22a​。但是这题找到那些 gcd⁡(a,x)≠agcd(a,x)=a 的数较为困难，因此我们维护每个区间的 $\text{lcm}$。如果一段区间的 $\text{lcm}$ 是 $x$ 的因数，那么这一段区间内所有数都是 $x$ 的因数，也就是说，这一段区间内的所有数不变，否则我们就一直找下去，就可以找到那些 gcd⁡(a,x)≠agcd(a,x)=a 的数了。这样的查找看起来很慢，其实对于每一个数都至多只有 $\log n$ 个数包含，所以均摊下来时间复杂度 $O(m\log n\log V)$，其中 V取 10^18。