线段树的扩展运用
在线段树本身信息动手脚的题一般就三步：
- 考虑怎么搞出具有幺半群性质的信息。（拆出多个信息（比如区间方差），或者想办法扩展一下信息来搞出结合律（比如 GSS⅓））
- 考虑怎么写 Pushup （假设左右儿子信息都已得到，然后看父亲节点怎么搞，边界为叶子节点）
- 考虑怎么写 Pushdown 和 Change。
如果是利用转化，把复杂的信息转化成简单的信息在线段树上维护的话，就只能靠灵感或者积累了。（比如区间加多项式一类的）
区间加多项式ψ(｀∇´)ψ
区间加多项式都是转化成差分数组之后前缀和，所以一般都是单点查询。
区间查询看看可不可做先。
区间加等差数列ψ(｀∇´)ψ
区间 \([l,r]\) 加等差数列，等同于在差分数组上的 \([l + 1,r]\) 做一次区间加 \(d\)，然后令 \(c[l] + \text{BEGIN}\)，\(c[r+1] - \text{END}\)。
\(\text{BEGIN,END}\) 分别是首项和末项。
单点询问只需要询问线段树上的 \(sum(1,pos)\) 即可。
例题: CF1661D Progressions Covering
区间加斐波那契ψ(｀∇´)ψ
这里鸽子了。
区间加等比数列ψ(｀∇´)ψ
这里鸽子了。
区间查某些东西ψ(｀∇´)ψ
区间 MEXψ(｀∇´)ψ
最简单的方法是考虑莫队。
如果要求在线就直接上主席树（权值线段树二分显然可以做全局，然后可持久化之后能转成区间的）
还有一种离线+线段树的暂时咕咕咕着，反正不如主席树或者莫队做法。
区间方差ψ(｀∇´)ψ
区间加法，区间询问方差。
考虑拆柿子：
定义平均数为 \(ava\)。
方差的定义是 \(\dfrac{1}{n} \sum\limits_{i = 1}^{n} (a_i - ava)^2\)
然后显然这个非常不好维护（不具有幺半群的性质，线段树没法维护），所以考虑拆开，变成几个具有幺半群性质的信息的组合。
于是如果不带修就只需要考虑维护区间和，区间平方和就行了。
然后这里有一个区间加法。
所以我们考虑维护一个 \(add\)。
显然区间加的时候和下放标记时，\(dat\) 的变化是一致的，就是考虑当区间每一个元素都被加上 \(v\) 之后，\(psum, sum\) 怎么变了。
然后区间和随便搞，考虑区间平方和 \(psum\)：
这个柿子很容易展开然后转化成能够 \(O(1)\) 下传，且具有时间轴上的结合律的信息，于是标记部分就做完了。
Pushup 很显然就是两个信息直接做加法，没了。
区间 sin 和ψ(｀∇´)ψ
思考好线段树的本质就行。
首先肯定要打 Tag，就是一个维护加法 Tag。
因为我要求的答案是 \(\sin\) 和，为了出现结合律，需要用和角公式。
所以信息只需要同时维护区间 \(\sin\) 和还有 \(\cos\) 和。
考虑一下区间加 \(v\) 之后一个区间的 \(\sin\) 怎么变了，方便下传标记还有更新信息。
先写出对于每一个元素的：
\(\sin (a + b) = \sin a \cos b + \sin b \cos a\)
\(\cos (a + b) =\cos a \cos b - \sin a \sin b\)
那么 \(\sum \sin(a_i)\) 就变成了 \(\sum \sin (a_i + v) = \sum (\sin a_i \cos v + \sin v \cos a_i)\)
展开：\(\cos v\sum \sin a_i + \sin v \sum \cos a_i\)，此时 独立了变量（维护的信息）和常量 \(v\)，很方便处理。
同理：\(\sum \cos (a_i) =\sum \cos(a_i + v) = \cos v\sum \cos a_i - \sin v \sum \sin a_i\)。
注意到一个坑点就是 \(\cos\) 还要用到原来更新前的 \(\sum \sin a_i\)，所以要提前记录一下。
然后 pushup 需要结合两个区间的 \(\sum \sin a_i, \sum \cos a_i\)，直接加起来就可以了。
然后就没了。
区间 GCDψ(｀∇´)ψ
单点修改ψ(｀∇´)ψ
这个很简单，因为 \(\gcd\) 满足结合律 : \(\gcd(a, b, c) = \gcd(a, \gcd(b, c))\)。
而且有幺元 \(0\)。
所以直接做就行了。
区间修改ψ(｀∇´)ψ
考虑转化成单点修改，直接维护差分数组，可以做到单点改。
然后发现 \(\gcd(a, b - a, c - b) = \gcd(a, b, c)\)，所以直接询问差分数组的 \(\gcd\) 就行了。
然后显然对于一个询问 \([l, r]\) 还要用到 \(a[l]\)，所以再开一个树状数组维护 \(a\) 就行了。
注意如果 gcd 的参数有负数就直接把 abs 带上去算就行。
扩展类ψ(｀∇´)ψ
维护矩阵乘法ψ(｀∇´)ψ
直接看这里就行了。
GSS 系列ψ(｀∇´)ψ
GSS1 & 3 区间最大子段和ψ(｀∇´)ψ
可以发现最大子段和没有明显的结合律。
不过我们试着假设左右儿子的最大子段和都已经求出，考虑怎么 Pushup。
那么其实也就三种情况，分别继承两边的，或者是左边取一段后缀，右边取一段前缀。
显然不可能有别的情况更优秀了。
所以需要维护一下每个子节点的最大前缀和，最大后缀和。
然后最大前缀和也需要考虑 Pushup，
显然就是左儿子的最大前缀和，或者是左儿子整体+右儿子的最大前缀和（因为子段是连续的，所以要选右儿子的最大前缀和就需要把左儿子整体选上）。
然后有没有一种可能，就是我右儿子选完最大前缀和之后，有没有可能后面还能找一些接到前缀后面比这个更大？
明显是蠢了，这里都是最大前缀和了，怎么可能嘛。
然后还有一种情况就是全部都选上。
最大后缀和同理即可。
注意如果一个区间都是负数，最大子段和应该是最大值，而不是上面三种情况的任意一种。
所以还需要维护一个区间最大值。
此时最大子段和就有结合律了。
GSS1 不带修，GSS3 带一个单点修，本质一样。
类区间最大子段和问题ψ(｀∇´)ψ
你有一个序列 \(a\)，一个序列 \(b\)。
你每次需要求一个区间内的一种贡献的最大值，定义为 \(\max\{a_x + b_y\}, x \le y\)。
这个东西其实也和最大子段和差不多，我们发现这个信息其实是可以合并的，我们直接维护答案，显然大区间的答案可能是两个小区间的答案之一，还有一种情况是从两个小区间各取一些组成答案。
所以对于每个节点，维护当前区间内最大的 \(a_x\) 和最大的 \(b_y\)，每次合并的时候，因为左右子树维护的区间是分开的，所以 \(x\le y\) 的条件也可以被满足。
然后答案就可以上传了，复杂度一个 log，也可以支持单点修改。
GSS4 区间开方（下取整），区间求和ψ(｀∇´)ψ
这题线段树也可以，虽然算是一个单独的 Trick，但毕竟是 GSS 系列的，就也写上了。
首先从数列分块入门 5 可以得到一个结论，就是区间开方的次数是很少的，如果 1e18 级别开 6 ~ 7 次就够了。
所以我们可以维护一个并查集，其中 \(pa(i)\) 表示，\([i, n]\) 之中，第一个不是 \(1\) 的数的下标。
初始指向自己。
然后对于每个询问我们直接暴力在 \(a(i)\) 上面单点开根号，如果遇到 \(1\) 就直接跳 \(pa(i)\)，因为开根号次数很少，然后多次操作之后要操作的数也很少。
并查集基本可以看作均摊 \(O(1)\) 的，所以这个东西复杂度非常优秀。
然后区间和再用一个树状数组维护就可以了，因为我们已经把区间开方转化为了单点开方。
这个就是一个很有意思的 Trick：对于这种操作多了之后“无效操作”变多的操作，可以考虑使用并查集记录一下每一个位置的下一个有效操作位置，把区间操作转化为单点操作。
几个同类型的题： Luogu2391 白雪皑皑，CF920F Sum and Replace，51Nod1743 雪之国度。