线段树
分治信息 线段树要求能维护的信息是含幺半裙。
线段树的重点是把区间分裂成若干个小区间，再把这些区间的信息合并。这些区间的信息也由更小的子区间信息合并而成。
对于一个区间 \([l,r]\)，将其分成两个子区间 \([l,\lfloor\frac{l+r}{2}\rfloor],[\lfloor\frac{l+r}{2}\rfloor+1,r]\)。把每个区间当做树上的节点，左端点等于右端点的区间就是叶子结点，除了叶子结点每个节点有两个儿子分别是他分裂的两个子区间。
复杂度分析：显然树的高度是 \(O(\log n)\) 的。而一个区间每层最多可以用四个小区间表示，所以区间查询也是 \(O(\log n)\)。
如题，已知一个数列，你需要进行下面两种操作：
- 将某一个数加上 \(x\)
- 求出某区间每一个数的和
懒标记
考虑线段树的区间修改，显然不可能给区间里的每个数暴力修改。采用标记思想，在修改的节点打上标记，下次经过他的时候把标记下传给他的儿子。这时标记和信息就需要可下传性。
例 2 洛谷3372 【模板】线段树 1
如题，已知一个数列，你需要进行下面两种操作：
- 将某区间每一个数加上 \(k\)。
- 求出某区间每一个数的和。
例 3 洛谷3373 【模板】线段树 2
如题，已知一个数列，你需要进行下面三种操作：
- 将某区间每一个数乘上 \(x\)
- 将某区间每一个数加上 \(x\)
- 求出某区间每一个数的和
这里需要注意的是标记合并的顺序，维护两个标记 \(add,mul\)，在加法的时候 \(add+=x\)，乘法的时候 \(add*=x,mul*=x\)。也就是先乘后加。
维护标记的重点就是需要保证下传标记后这个节点的信息必须是正确的
标记永久化
刚刚说的懒标记是需要下传的，我们也可以让标记永久存在在节点上，查询的时候把遍历到的节点上的标记合并即可。
如题，已知一个数列，你需要进行下面两种操作：
- 将某区间每一个数加上 xx；
- 求出某一个数的值。
位运算线段树
常数更小的非递归线段树，主要用来卡常数（貌似代码写起来也更短）。但是 zkw 线段树没法处理有运算符优先级的问题（比如线段树模板2）。
把线段树填充成满二叉树，那么就可以直接找到叶子结点。我们令 \(N\) 是叶子结点个数，那么 \(N+i\) 就是第 \(i\) 个数对应的叶子结点。为了最后一个节点不超出边界，我们这么得到 \(N=2^{\lceil\log_2{n+1}\rceil}\)。
单点修改的时候不停的跳父亲即可。
考虑区间询问和修改。我们记 \(lc=l-1+N,rc=r+1+N\)，这两个指针不断的往上跳，直到跳到两者父亲相同（或者一个是 \(0\)，一个是 \(1\)）停止。这时 \(lc\) 的每个从左儿子跳上来时的右儿子或者 \(rc\) 的每个右儿子跳上来的左儿子，的并就是我们要找的区间。其实根据我们刚刚的推论每层最多只有 \(4\) 个。
对于修改，显然我们需要标记永久化。记录每个节点里面有多少被修改的节点，更改值即可。
这样子写线段树 1：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n, m, N;
ll sum[maxn << 2], add[maxn << 2];
void modify(int l, int r, ll v)
{
int lnum = 0, rnum = 0, len = 1, lc, rc;
for (lc = l - 1 + N, rc = r + 1 + N; lc ^ rc ^ 1; lc >>= 1, rc >>= 1, len <<= 1)
{
sum[lc] += v * lnum;
sum[rc] += v * rnum;
if (~lc & 1) sum[lc ^ 1] += len * v, add[lc ^ 1] += v, lnum += len;
if (rc & 1) sum[rc ^ 1] += len * v, add[rc ^ 1] += v, rnum += len;
}
for (; lc; lc >>=1 , rc >>= 1)
{
sum[lc] += v * lnum;
sum[rc] += v * rnum;
}
}
ll query(int l, int r)
{
int lnum = 0, rnum = 0, len = 1, lc, rc;
ll ret = 0;
for (lc = l - 1 + N, rc = r + 1 + N; lc ^ rc ^ 1; lc >>= 1, rc >>= 1, len <<= 1)
{
ret += add[lc] * lnum;
ret += add[rc] * rnum;
if (~lc & 1) ret += sum[lc ^ 1], lnum += len;
if (rc & 1) ret += sum[rc ^ 1], rnum += len;
}
for (; lc; lc >>=1 , rc >>= 1)
{
ret += add[lc] * lnum;
ret += add[rc] * rnum;
}
return ret;
}
int main()
{
scanf("%d%d", &n, &m);
for (N = 1; N <= n + 1; N <<= 1);
for (int i = N + 1; i <= N + n; i++) scanf("%lld", sum + i);
for (int i = N - 1; i; i--) sum[i] = sum[i << 1] + sum[i << 1 | 1];
while (m--)
{
int op, l, r;
ll x;
scanf("%d%d%d", &op, &l, &r);
if (op == 1)
{
scanf("%lld", &x);
modify(l, r, x);
}
else
{
printf("%lld\n", query(l, r));
}
}
return 0;
}
大概快了 100 ms。
更复杂的信息
例 5 P4513 小白逛公园
序列，单点修改，询问区间最大子段和
对于每个区间，维护一个左边的最大前缀，右边的最大后缀，以及区间内部的答案。每次合并的时候，即答案选取左子区间的max，右子区间的max，或者左子区间的最大后缀，右子区间的最大前缀即可。
\(n\) 个点，\(m\) 个询问。给你一棵树的括号序列，输出它的直径。
有 \(m\) 次询问，每次询问表示交换两个括号，输出交换两个括号后的直径（保证每次操作后都为一棵树）
容易发现树上一条路径一定形如 ))...)((...(。也就是对于任意子段，去掉匹配了的括号后还剩下的部分。而这个东西还是不太好表示，我们有如下引理：
这个值等于 \(\max\limits_{k=l}^{r-1}s_{k+1,r}-s_{l,k}\)，其中 \(s_{i,j}\) 代表把 ( 看成 \(1\)，) 看成 \(-1\) 后区间 \([i,j]\) 的和。
证明 一定可以找到最后一个 )，当 \(k\) 取到这个位置时 \(s_{k+1,r}-s_{l,k}\) 显然就是答案。接下来证明这个值是最大的。在这个体系里面所有被匹配掉的括号贡献都是 \(0\)，最后没被匹配掉的括号，\(k\) 往左往右都会变小，得证。
那么现在就是要求 \(\max\limits_{l,r} \max\limits_{k\in [l,r)}s_{k+1,r}-s_{l,k}\)，即 \(\max\limits_{l,k,r}s_{k+1,r}-s_{l,k}\)。类似最大子段和，这个也可以用线段树来维护。
简单分类讨论 \(k\) 是取在区间中点的左边还是右边即可。
权值线段树
线段树的节点代表值域，每个节点相当于一个桶，用来表示一个区间的数的出现次数。
动态开点
有的时候用不到的点可以不建出来，每个节点维护儿子指针，当遍历到其儿子时再建儿子那个点。空间复杂度变为 \(O(n\log n)\)。
主席树
主席树是一种算法
把上一个阶段的线段树继承过来，然后对于要修改的部分新建节点替换旧的节点。思想类似动态开点的线段树。
李超树
前缀线段树
猫树
线段树合并分裂
线段树合并是指合并多棵动态开点权值线段树的一种算法，把相同节点的信息合并，其余节点继承。每个插入的节点只会被合并一起，所以总的时空复杂度都和动态开点的线段树一致。
P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并
P5327 [ZJOI2019]语言
P5298 [PKUWC2018]Minimax
P6773 [NOI2020] 命运
线段树优化建图
如果连边是 \([a,b]\to [c,d]\)，那可以用线段来优化建边。其实就是虚点的思想，用线段树上 \(log\) 个区间来拆解要连边的区间。
进行单点与单点连有向边，进行单点与区间连有向边，进行区间与单点连有向边。然后求最短路。
建两棵树，一棵从父亲连向儿子叫做 A，另一颗从儿子连向父亲是 B。当要连边的时候从 B 连到一个虚点，再从虚点连向所有 A 树上的区间连边。
例
https://www.luogu.com.cn/problem/P5025
在一条直线上有 \(n\) 个炸弹，每个炸弹的坐标是 \(x_i\)，爆炸半径是 \(r_i\)，当一个炸弹爆炸时，如果另一个炸弹所在位置 \(x_j\) 满足：\(\mid x_j-x_i\mid \le r_i\)，那么，该炸弹也会被引爆。
现在，请你帮忙计算一下，先把第 \(i\) 个炸弹引爆，将引爆多少个炸弹呢？
很直观的想法是直接把每个点向能炸到的点都连一条边，然后缩点dag再dp一下求出每个点能炸到的最左端和最右端。
我们发现每个点能引爆的点一定在某个区间内，所以我们容易想到线段树优化建图。
建一棵线段树，从父节点连向它的两个子节点一条有向边。
对于每个节点，计算出它自己爆炸的范围，然后向线段树上代表这个区间的那些点连边。
这个节点其实用线段树上的叶节点即可，不用再建新的节点。
然后跑一遍tarjan强连通分量缩点，每个新点要记录改分量里能炸到的最远的左右端点。
之后我们还有跑一点dag dp，用每个节点能到达的点更新其左右端点。
注意这里不能直接拓扑，要在反图上拓扑，因为这里直接拓扑时孩子是没有更新的（虽然能过。。。）
查询时直接返回对应scc的左右端点的差即可。
segmentree beats
线段树分治
平衡树
所有平衡树都在干一件事——让树高（期望或均摊）尽量小。
fhq-treap
treap 是堆+二叉搜索树的合称。给每个点随机分配一个权值，使treap同时满足堆性质和二叉搜索树性质。fhq treap不需要旋转，重点就两个操作：merge 和 split。
这篇博客写得很全：https://www.luogu.com.cn/blog/85514/fhq-treap-xue-xi-bi-ji
关于fhq-treap复杂度的证明：
在引入了随机优先级后，Treap 就相当于以随机顺序插入得到的二叉搜索树，
考虑每个节点 \(i\) 在什么情况下会成为 \(x\) 的祖先。即 \(i\) 到 \(x\) 之间的节点优先级都小于 \(i\)。那么 \(x\) 的期望深度即为 \(1+\sum_{i=1}^{x-1}\frac{1}{x-i}+\sum_{i=x+1}^{n}\frac{1}{i-x}=O(\log n)\)。
替罪羊树
思想很简单，设置一个平衡因子 \(\alpha\)，如果一个点的某个儿子，占到了子树大小的α，则认为不平衡，重构这个子树。别的不说，知道这个复杂度是均摊证明的就行。
splay
学习笔记：https://baijiahao.baidu.com/s?id=1613228134219334653&wfr=spider&for=pc
每次对一个节点进行操作的时候把这个点旋转至根
动态开点平衡树
也就是把所有没用到的节点放到一起，用到了再把其断开。
例 P3285 [SCOI2014]方伯伯的OJ
有一个长度为 \(n\) 的序列，以及 \(m\) 次操作。
- 把 \(x\) 的编号换成 \(y\) 并输出 \(x\) 的排名。
- 把 \(x\) 提升到第一
- 把 \(x\) 降到最后
- 查询排名为 \(k\) 的人
\(1\le n\le 10^8,1\le m\le 10^5\)。
split 的部分我们每个节点其实相当于维护了一段。
动态开点平衡树的具体操作就是如果我们需要搞一个用户，我们先找到它所在的节点，这个节点可能代表一段连续编号的区间，并且一定包含改用户，然后把这个节点分裂成三个节点（可以新建三个节点也可以垃圾回收），再merge会平衡树里。可以发现这样做的空间复杂度是 \(O(m)\) 的。
可是这道题还比较毒瘤的一点是它只告诉你用户编号，这时我们需要一个映射把用户编号映射到平衡树上的节点，而我们又不可能一对一的映射，因为这在分裂节点时的时间复杂度是不对的。有一个trick是只记录每个节点右端点所在节点，然后再map中二分找，找到第一个大于等于当前询问编号的肯定就是和当前询问编号在同一节点的。
可持久化
treap 的复杂度不依赖均摊，所以可以直接可持久化。需要注意的是在split，merge，pushdown这些需要修改节点权值的时候，就需要新建节点（其实如果merge之前必然split的话就不需要新建）。
需要注意的是，假如在可持久化的过程中涉及到复制一棵Treap，复制出来的Treap的随机优先级会与原本的Treap完全一样，这可能会导致后续操作的Treap不再平衡。目前OI界中常用的解决方法是，不存储节点的随机优先级，而是在需要比较优先级时再依据节点的子树大小随机地返回结果。
例
173. 【WC2016】鏖战表达式
可持久化
KD TREE
动态树
分块
杂项
参考
原文链接: https://www.cnblogs.com/zcr-blog/p/17012210.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/313761
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
