NOI 一轮复习 III：数据结构
知识清单：
阅读须知：
- 作者数据结构水平很低。
- 由于上条，所以你会发现本文中只有基础内容。
- 本文中 \log 一般指以 2 为底的对数。
1. 简单工具
这一部分学习一些结构简洁的数据结构工具。
线段树
线段树是一种非常基础且功能强大的树形数据结构，并且有非常多的扩展。
线段树用于维护一个长度为 n 的序列，是一个包含 2n-1 个点的完满二叉树结构（非叶结点有恰好两个儿子），每个结点表示一个区间，n 个叶结点对应长度为 1 的区间（即原序列中的各个元素），非叶结点对应的区间为两个儿子的区间并，每个结点的儿子有左右之分，且前序遍历中叶结点序列对应的位置序列恰为 1,2,\ldots,n。
狭义的线段树（或标准线段树）要求结点 [l,r] 的左儿子为 [l,mid]，右儿子为 (mid,r]，其中 mid=\lfloor\dfrac{l+r}{2}\rfloor，而广义的线段树中 mid 可以是 [l,r) 中任意一个整数，下文的线段树一般是狭义的。
线段树的基本性质：
性质 1：任意两个结点的区间或者为包含关系，或者不交。
证明：显然。
接下来的性质依赖于区间拆分的定义：
区间拆分：区间 [l,r] 可以表示为线段树上若干个区间的不交并，称这些区间构成 [l,r] 的区间拆分。
我们将先介绍求出任意区间的一个区间拆分的算法：
这是一个递归过程，记为 Solve(l,r,xl,xr)，表示当前递归到的结点代表区间 [xl,xr]，我们需要求解 [l,r]\cap [xl,xr] 在这个结点子树中的区间拆分：
- 如果 [l,r]\cap [xl,xr]=\varnothing，则直接返回 \varnothing；
- 如果 [l,r]\cap [xl,xr]=[xl,xr]，则直接返回 \{[xl,xr]\}；
- 否则，返回 Solve(l,r,xl,mid)\cup Solve(l,r,mid+1,xr)。
性质 2：任何一个包含于 [1,n] 的区间的区间拆分存在，且大小最小的区间拆分唯一。
证明：根据上面的算法，显然可以求出一个区间拆分。
上面的算法中第一种分类和第三种分类是没有问题的，而第二种情况中我们可以选择不返回单独区间而递归两边，但这会导致至少需要两个区间来代替一个区间 [xl,xr]，区间拆分变大。
因此上面的算法求出的就是唯一存在的最小区间拆分。
性质 3：最小区间拆分的大小不超过 2\log n+c，其中 c 是与 n 无关的常数。
证明：这是一个直观的证明。
首先我们证明两个简单的引理：
引理 1：若 l\leq xl 或 r\ge xr，则 |Solve(l,r,xl,xr)|\leq \log (xr-xl+1)+c。
若 xl=xr 显然，否则归纳，l\leq xl 和 r\ge xr 对称，我们以前者为例：
- 如果 r<xl 则 |Solve(l,r,xl,xr)|=|\varnothing|=0；
- 如果 xl\leq r\leq mid 则 |Solve(l,r,xl,xr)|=|Solve(l,r,xl,mid)|\leq \log(xr-xl+1)+c；
- 如果 r>mid 则 |Solve(l,r,xl,xr)|=|Solve(l,r,mid+1,xr)|+1\leq \log(xr-xl+1)+c；
引理 2：递归过程中至多存在一个点 [xl,xr] 使得 xl<l\leq mid< r<xr。
证明：如果不满足上述条件，两侧只会至多递归一边（另一边是前两种平凡情况之一）。
那么我们可以找到第一个满足上述条件的点（若不存在则结论成立），可以发现它会向两边递归，并且两边都是符合引理 1 形式的，在引理 1 的分析过程中发现不再存在满足条件的点。
符合这个条件的点称为分治点。
由上述两个引理：
- 如果没有分治点，那么 |Solve(l,r,1,n)|=\log n+C，因为始终不会向两边递归（或至少其中一边是平凡情况）；
- 如果有分治点，那么找到它 [l_0,r_0]，由于 [l_0,mid] 和 (mid,r_0] 都是符合引理 1 形式的区间，所以拆分出不超过 \log (mid-l_0+1)+\log (r_0-mid+1)+2c\leq 2\log \lceil \dfrac{n}{2}\rceil+2c\leq 2\log n+2c 个区间，这里 2c 是与 n 无关的常数。
稍加精细分析也许可以得到一个稍好的界（例如 c\leq 2），但我们这里只是尝试说明其量级是 2\log n 级别的。
我们可以用线段树解决一系列维护序列的数据结构问题。
最简单的形式是区间查询，即询问给定序列的某一区间 [l,r] 的相关信息，如果我们可以对每个区间维护一套信息，称为 f([l,r])，使得 f(\varnothing) 和 f([l,l]) 容易计算，并且存在一种运算可以合并位置上相邻的两个区间的信息，即可以定义 + 使得 f([a,c])=f([a,b])+f([b+1,c]) 能够快速计算，那么我们就可以用线段树来对于给定的区间快速求出它的一套信息。
具体地，我们维护线段树上每个区间的 f 值，可以由其两个儿子的 f 相加得到。
令 Solve(l,r,xl,xr)=f([l,r]\cap [xl,xr])，那么：
- 如果 [l,r]\cap [xl,xr]=\varnothing 或 [l,r]\cap [xl,xr]=[xl,xr]，直接按照已有信息返回；
- 否则，返回 Solve(l,r,xl,xr)=Solve(l,r,xl,mid)+Solve(l,r,mid+1,xr)。
根据区间拆分的性质，由于拆分出的区间只有 2\log n+c 个，所以第二种分类中的分治也只有 2\log n+c 个。
设信息合并复杂度为 T，则进行一次查询的复杂度是 O(nT\log n)，而初始化复杂度为 O(nT)。
例题 1：
维护一个长度为 n 的序列，支持 m 次查询一个区间的和，乘积，最值，最大子段和，最大不相邻子集和（选择区间的一个子序列使得相邻两个元素不同时选的最大和）。
和：sum(l,r)=sum(l,mid)+sum(mid+1,r)。
乘积，最值类似。
最大子段和：令 pre(l,r),suf(l,r),mx(l,r) 分别表示 [l,r] 的最大前缀和，最大后缀和，最大子段和。
pre(l,r)=\max(pre(l,mid),sum(l,mid)+pre(mid+1,r))
suf(l,r)=\max(suf(mid+1,r),sum(mid+1,r)+suf(l,mid))
mx(l,r)=\max(mx(l,mid),mx(mid+1,r),suf(l,mid)+pre(mid+1,r))
最大不相邻子集和：令 f(l,r,0/1,0/1) 表示 l,r 强制选/不选时的区间最大不相邻子集和，转移比较简单。
时间复杂度为 O((n+m)\log n)。
从上面的例子中，我们发现，如果要对区间求和，积，最值，最大公因数，点积等满足结合律的运算时，都可以用线段树来维护，这类满足结合律的运算称为对应数集上的半群运算。
线段树当然不止能解决静态的区间查询问题，还可以支持多样的修改。
最简单的情形是单点修改，注意到修改一个点的值只会对线段树上其对应的叶结点的所有祖先信息产生影响，所以我们暴力进行更新，复杂度即为 O(T\log n)。
还可以支持区间修改，区间修改的形式是多样的，包括区间加，区间赋值等。
一般我们将修改的区间进行拆分，转化为 \log n 次对线段树上的结点代表的区间进行修改，然后使用一些标记进行维护。
这里采用的手法叫懒标记，我们对每个点额外维护一套标记信息 g(l,r)，在修改 [l,r] 时我们不需要对区间中每个点都修改一遍，而是先将修改的信息缓存在 g(l,r) 中，此后无论是修改还是询问，只要经过这个点我们就对标记进行一次下放：即用 g(l,r) 更新 g(l,mid) 和 g(mid+1,r)，当前这也会对 f(l,mid) 和 f(mid+1,r) 造成影响。
在实现时我们定义 spread 过程和 pushdown 过程，其中 spread 过程把一个标记信息赋予一个点，而 pushdown 过程会调用 spread 修改一个点的两个儿子的信息，并将当前点的标记信息清零。
例题 2：
维护一个长度为 n 的序列，支持 m 次操作，操作包括区间赋值，以及查询一个区间的和，乘积，最值，最大子段和，最大不相邻子集和。
这里的标记信息非常简单：g(l,r) 表示 [l,r] 被整体赋的值，若当前 [l,r] 没有被限制赋值，那么 g(l,r) 没有定义。
当 g(l,r) 有定义时，下放过程如下：
- 令 g(l,mid)=g(mid+1,r)=g(l,r)；
- 重新计算区间和，区间积，区间最值，区间前缀后缀子段和等信息，由于所有数都一样，所以这是容易计算的。
时间复杂度为 O((n+m)\log n)。
例题 3：
维护一个长度为 n 的序列，支持 m 次操作，操作包括区间加，区间乘，以及查询区间和。
这里的标记信息 g(l,r) 是一个二元组 (add,mul)，表示当前区间每个数都应该先乘上 mul 再加 add。
此处要说明标记信息的一个原则：越浅的标记越新，正如上题中浅的赋值标记可以直接覆盖深的赋值标记。
那么在本题中，我们在下放标记时，也是对于儿子的标记信息先乘 mul 再加 add，因为当前点的信息更新，所以当前点的乘法标记会对儿子的加法标记有倍增效应。
时间复杂度为 O((n+m)\log n)。
一些常见的标记下放还有很多，这里稍微列举一下，不详细说明方法了：
- 区间加标记对区间 k 次方和的影响，在 O(k) 时间内计算；
-
-
- 一个基本标记的集合版：区间赋值，区间取相反数，区间最大子段和并给出方案，你需要不下于 10 个整数来维护一个区间的信息。
矩阵乘积
对于一些只包含单点修改的题目，有时线段树维护的区间信息满足一定的线性性和递推性，可以用一种比较无脑的形式表示出来：矩阵。
而这种用矩阵乘积维护递推的技巧似乎也被称作“动态 DP”。
一般地，我们用一个行向量 \bold v 表示一个状态，而序列中的一个元素看作对 \bold v 的一个线性变换——也就是一个矩阵 M。
那么我们要访问一个区间的一些信息，可以定义一个初始状态 \bold v_0，然后计算区间矩阵乘积，用 \bold v_0 去乘它，就得到的最终状态，也就是我们需要的信息。
注意到可以用矩阵乘法（无论是 \times,+ 还是 +,\min/\max），都蕴含了信息合并满足结合律这一前提。
有趣的是，许多时候矩阵乘积并不是一道题目最快的解法，因为通常矩阵中包含冗余零位，使得矩阵乘法的复杂度大于最优的信息合并的复杂度。
例题 4：[Luogu P6373] IOI 计数
维护一个包含 I,O 两种字符的序列，支持单点修改，以及查询一个区间中子序列 IOI 的出现次数。
用四维向量 \begin{bmatrix} a\quad b\quad c\quad d\end{bmatrix} 表示信息：之前已经有 a 个子序列 I，b 个子序列 IO，c 个子序列 IOI，d 固定为 1 便于转移。
对于字符 I，可以从 d 转移到 a（多了一个 I），可以从 b 转移到 c（IO 后加一个 I），所以其矩阵为：
\begin{bmatrix} 1\quad 0\quad 0\quad 0 \\
0\quad 1\quad 1\quad 0 \\
0\quad 0\quad 1\quad 0 \\
1\quad 0\quad 0\quad 1\end{bmatrix}
而对于字符 O，只能从 a 转移到 b，所以其矩阵为：
\begin{bmatrix} 1\quad 1\quad 0\quad 0 \\
0\quad 1\quad 0\quad 0 \\
0\quad 0\quad 1\quad 0 \\
0\quad 0\quad 0\quad 1\end{bmatrix}
随后我们求区间矩阵乘法就可以得到答案（答案为乘积的第四行第三列，由于最初只有 d 是 1）。
时间复杂度为 O(n\times 4^3\log n)，本题的常规做法是暴力维护区间中 a,b,c 的值，和矩阵乘法本质相同。
势能分析
正常线段树的分治过程中当 [l,r]\cap [xl,xr]=[xl,xr] 时就会停止，但有时我们无法对任意线段树上的区间进行信息的更新，也就是说即使满足 [l,r]\cap [xl,xr]=[xl,xr] 也有可能继续递归，直到这个区间 [xl,xr] 满足某些条件，这时线段树的复杂度就需要依赖一些势能的分析。
例题 5：[Luogu P4145] 花神游历各国
维护一个长度为 n 的序列，支持 m 次操作，操作包括区间开方，以及查询区间和。
用线段树维护数列，线段树一个区间的势能定义为区间最大值要开多少次平方才能变成 1。
修改时，如果当前区间势能为 0，表示全是 1，不用修改。
否则，暴力递归两边，并维护区间和。
可以发现，由于一个数开方后缩减速度很快，初始每个点的势能都是很小的，设最大势能为 C，总势能为 nC。
每次操作定位到 O(\log n) 个区间，此后每次递归都会使得当前区间的势能减小 1（因为最大值也被开方了），而势能非负，所以总的时间复杂度为 O(m\log n+nC)。
例题 6：[雅礼集训 2017] 市场（可见 LOJ）
维护一个长度为 n 的序列，支持 m 次操作，操作包括区间加，区间除一个数下取整，以及查询区间最小值和区间和。
用线段树维护数列，区间上维护最大最小值，区间和还有标记，修改时，区间加直接做，而区间除时，递归到线段树上某一区间，如果这一操作等价于区间加（也就是最大和最小值变化量相等），那么就直接打加法标记，不用递归。
时间复杂度不知道（有空再说）。
例题 7：[BZOJ 5312] 冒险
维护一个长度为 n 的序列，支持 m 次操作，操作包括区间按位或一个数，区间按位与一个数，以及查询区间最大值。
用线段树维护数列，记录区间的或和与。
可以发现，如果一个区间或/与操作对整个区间或和整个区间与的变化量相等，那么就等价于一次区间加。
所以我们和上题类似，不断递归直到出现上面那种情况，然后打区间加法标记。
时间复杂度不知道。
线段树结构题全家桶
经常有这样一类问题：模拟线段树上的若干操作，然后查询相关的计数信息。
这里给出一系列结论和处理手法，用于解决这一类问题，下面的描述一般对广义线段树都成立。
结论 1：[1,n] 的广义线段树内 [l,r] 的区间定位数为 2\times (r-l+1)-|S|，其中 |S| 表示线段树上完全包含于 [l,r] 的区间数量。
注意这里的区间定位数就是 [l,r] 最少拆成多少个线段树上区间的并。
证明：
考虑提取出所有 S 中结点，即完全包含于 [l,r] 的结点，容易发现这构成了一个完满二叉树森林，而根的个数就是 [l,r] 的区间定位数。
而完满二叉树中结点数等于 2\times m-1，其中 m 为叶子的个数，而叶子的总数是 r-l+1，所以总点数 |S| 就是 2\times (r-l+1)-ans，其中 ans 就是连通块数，也就是根的个数，[l,r] 的区间定位数，所以 ans=2\times (r-l+1)-|S|。
例题 8：[THUPC 2021 初赛] 线段树
求 [1,n] 的标准线段树中所有 [l,r] 的区间定位数之和（1\leq l<r\leq n）。
考虑直接套式子，将 2\times (r-l+1) 和 |S| 分开考虑。
\sum\limits_{l=1}^n\sum\limits_{r=l}^n2\times (r-l+1)=2\times\sum\limits_{len=1}^nlen\times(n-len+1)
令 s_i(n) 表示 \sum\limits_{j=1}^n j^i，那么上式等于：
2\times \Big((n+1)\times s_1(n)-s_2(n)\Big)
后面这个 |S|，设线段树结点集合为 V，点 x 的左右端点为 l_x,r_x，那么：
\sum |S|=\sum\limits_{x\in V}l_x\times (n-r_x+1)
设 c(n),sl(n),sr(n),slr(n) 分别表示 [1,n] 线段树中的点数，左端点和，右端点和，左端点乘右端点之和，那么：
\sum |S|=(n+1)\times sl(n)-slr(n)
考虑分治，用左边加上右边加上根即可，注意右边需要有个将所有 l,r 平移的过程，但是这个操作可以通过我们已有的信息和平移量直接得出。
然后使用记忆化搜索即可，时间复杂度为 O(\log n) 或 O(\log^2 n)。
结论 2：（广义线段树区间定位的结构）在 [1,n] 的广义线段树上，[l,r] 的区间定位由以下两部分组成，设 S 是 [l-1,l-1] 和 [r+1,r+1] 对应结点（后两者分别称为 L,R）的 LCA：
- L\to S 路径上所有左偏儿子的兄弟，不包括 S 的右儿子；
- R\to S 路径上所有右偏儿子的兄弟，不包括 S 的左儿子。
左偏儿子和右偏儿子分别指这个点是其父亲的左/右儿子。
例如，在 [1,10] 的标准线段树上，[3,8] 的区间定位如下，黄色表示区间定位中的区间，其中 [3,3] 是 [2,2] 的祖先 [1,2] 的右兄弟；[4,5] 是 [2,2] 的祖先 [1,3] 的右兄弟，[6,8] 是 [9,9] 祖先 [9,10] 的左兄弟，都符合上面的描述：
这个结论主要难在比较抽象，举了一个例子后应该就很好理解了，值得一提的是，这个 S 并不一定是 [l,r] 区间定位时的分治点，例如在上面的标准线段树中求 [6,9] 的区间定位，S 仍然是根而分治点是 [6,10]。
此外，如果 l=1 或 r=n，我们可以在广义线段树上额外建出 0 和 n+1 这两个位置，如图：
一般地，我们如何刻画形如结论 2 刻画的这些区间呢？不难发现左右是相对独立的，可以分开考虑。
首先找到 [l-1,l-1] 和 [r+1,r+1] 对应的点 L,R 以及它们的 LCA S。
设 LFT(P) 和 RGT(P) 分别表示 P 的所有祖先中左偏儿子的右兄弟集合，以及右偏儿子的左兄弟集合。
那么 [l,r] 的区间定位集合就是 (LFT(L)\backslash LFT(l_S))\cup (RGT(R)\backslash RGT(r_S))，其中 l_S,r_S 分别是 S 的左右儿子。
例题 9：[ZJOI 2017] 线段树
给定 [1,n] 的广义线段树，有 m 组询问，每组询问给定区间 [l,r] 和线段树上结点 p，求 p 到所有 [l,r] 定位出的区间对应结点的距离和。
本题题解大多用到了额外的树形数据结构进行维护，实际上是不需要的。
设 [l,r] 的区间定位集合为 S，那么：
\sum\limits_{q\in S}dis(p,q)=|S|\times dep_p+\sum\limits_{q\in S}dep_q-2\sum\limits_{q\in S}dep_{\operatorname{LCA}(p,q)}
根据我们前面提到的对 S 的刻画方法，设 Cl_p,Cr_p,Sl_p,Sr_p 分别表示 p 的所有祖先中左偏/右偏儿子的右兄弟/左兄弟的数量/深度和，然后 |S| 和 \sum\limits_{q\in S}dep_q 都可以通过这四个数组的简单差分求出。
而最后一项是 LCA 的深度，这需要一些精细讨论：
- 如果 p 与 [l-1,l-1] 的 LCA（记为 L_1）是 [l-1,l-1] 与 [r+1,r+1] 的 LCA（记为 L_0）的祖先，那么与左链上所有定位出的 q 的 LCA 都是 L_1，否则在 L_1 以下的点与 p 的 LCA 是 L_1，其它点与 p 的 LCA 就是它的父亲（但如果恰好是 L_1 的一个儿子，那么 LCA 是它自己）；
- 右边的情况类似。
上述情况都是也可以通过 L_1 对应的四个数组和 [l-1,l-1] 进行差分容易得到的。
所以最终我们唯一的复杂度瓶颈就变成了求三个 LCA，而这事实上可以做到线性。
时间复杂度 O((n+m)\log n) 到 O(n+m)。
接下来再介绍一个刻画广义线段树区间定位的更有力且本质的结构。
对于 [l,r] 的区间定位，首先找到 [l,r] 的分治点 S（就是 [l,l] 和 [r,r] 的 LCA，如果有分治点肯定是这个点，否则就没有分治点），那么 [l,r] 的区间定位要么是 S 本身，要么是 S 左儿子的一部分拼上右儿子的一部分（结论 2 中的两条）。
例如我们考虑左儿子的部分，上面已经说明了这部分定位出的区间一定都是右偏的（父亲的右儿子），我们不妨先把这些右偏结点（以及根结点）单独拿出来，每个点的父亲定义为包含它的最小区间，如下图所示，不妨将这个树形结构称为逻辑右偏树：
这个树形结构和树状数组关系极为密切，但这里暂不题及，不过我们可以发现的是以每个下标为左端点的点是唯一的，设以 l 为左端点的区间对应的结点称为 p_l。
接下来是重要的一步：我们定义右偏树上一个结点 [l,r] 的跳跃链接为 p_{r+1}（如果 r=n 可以定义为没有这个链接，也可以建立一个虚点 [n+1,n+1]）。
将所有的跳跃链接拿出来，构成了一个森林，不妨称为跳跃树，上图所示的逻辑右偏树的跳跃树如下图所示：
那么我们有：
结论 3：区间 [l,n] 在广义线段树上的区间定位集合就是跳跃树上 p_l 的祖先集合。
这是因为 [l,n] 是一段后缀，所以所有定位出的区间一定是右偏结点（或根结点），而包含 l 却不包含 l-1 的唯一右偏点是 p_l，假设它代表区间 [l,r_0]，那么下一步我们就从 r_0+1 出发，这无非是跳到了 p_l 在跳跃树上的父亲 p_{r_0+1}。
同理，我们还可以定义逻辑左偏树和它对应的跳跃树。
在 Shadowice1984 的博客 中提到了建立跳跃树的一种方法：在广义线段树上 DFS，令右儿子的父亲和当前点的父亲相同，左儿子的父亲为右儿子，最后删除所有左偏结点，就得到了逻辑右偏树的跳跃树。
而对于区间 [l,r] 的区间拆分，无非是找到其分治点 S，然后在右偏树的跳跃树上 p_l 的所有不越过 S 左儿子的祖先，以及左偏树的跳跃树上 p'_r（以 r 为右端点的区间）的所有不越过 S 右儿子的祖先。
通过这点，我们实现了：将 [l,r] 的区间定位集合分成了两棵不同树上的两条祖先链。
我们可以用这点完成上面的例题 9，详情可以看上面的博客链接，不过他的做法带了 \log。
而真正让我注意到这一结构的是一道集训队论文题，下面略作分享：
例题 10：[2017 集训队互测] 被操纵的线段树
给出一个 [1,n] 的广义线段树，支持 m 个操作：
- 给定 l,r，查询 [l,r] 的区间定位数（包含的区间数量）；
- 对树中某个结点进行一次旋转，旋转类似 Splay 中的定义，如下图（图来自原论文）：
强制在线。
如果我们直接使用结论 1，可以发现一次旋转只会影响常数个区间，所以我们用数据结构维护所有区间，需要支持修改以及查询 [l,r] 包含的区间数量，相当于三维偏序。
由于强制在线，所以我们需要用树套树解决，时间和空间均为 O((n+m)\log^2 n)。
想要进一步优化，就需要用到上面说的跳跃树的概念，事实上这也很简单：为了支持修改，我们只需要用 LCT 维护两个跳跃树，就可以支持旋转操作。
而查询时我们需要在 LCT 中某个点的祖先链上二分，只需要 access 之后在 Splay 上二分即可。
这种做法时间复杂度为 O((n+m)\log n)，空间复杂度为 O(n)，明显更优。
有趣的是，论文中还提到了结论 2 的做法，看来结论 1,2,3 分别能给出本题的三个不同做法，非常高妙。
接下来介绍的时在许多 ZJOI 题目中出现的套路：
区间定位的五类点：在进行 [l,r] 的区间定位时，我们考虑懒标记的下放，可以按照这一过程对点上标记的影响将结点分成五类：
- 与 [l,r] 有交且不被 [l,r] 包含的区间，即访问到并继续递归的结点；
- 区间定位点；
- 第 2 类点的真后代；
-
- 第 4 类点的真后代。
我们还是以上面的例子为例，在 [1,10] 的标准线段树上做 [3,8] 的区间定位，得到的五类点分别用红橙黄绿蓝标记：
考虑进行一次 [l,r] 的区间定位，并给所有定位点打上懒标记，下传沿途的标记这一过程对五类点的影响：
- 红点：不管之前什么样，现在肯定没标记；
- 橙点：不管之前什么样，现在肯定有标记；
- 黄点：标记情况维持不变；
- 绿点：如果之前它的祖先（包括自己）至少一个结点有标记，那么它就会带上标记，否则它没有标记；
- 蓝点：标记情况维持不变。
绿点的情况最为麻烦，如果我们要维护所有点的标记情况，那么需要为此多维护一个变量。
设 f_i 表示 i 是否有标记，g_i 表示 i 的所有祖先（包括自己）是否至少一个有标记，f'_i,g'_i 是操作前的情况，则操作后的 f_i,g_i 的所有情况如下列出：
- 红点：f_i=g_i=0；
- 橙点：f_i=g_i=1；
- 黄点：f_i=f'_i,\ g_i=1；
- 绿点：f_i=g_i=g'_i；
- 蓝点：f_i=f'_i,\ g_i=g'_i。
例题 11：[ZJOI 2020] 传统艺能
给定一个 [1,n] 的广义线段树，每次操作等概率选取一个区间 [l,r]，将其区间定位集合中的区间打上懒标记，同时下传沿途标记，求 k 次操作后期望有多少个点被打上标记。
对每个点 p 求出它最终有标记的概率，相加即为答案。
我们可以先算出 p 在 [l,r] 的定位过程中属于红橙黄绿蓝每一类点的概率 p_1,\ldots,p_5，然后将操作对 f_p,g_p 的影响写成一个矩阵，由于有 1 的出现所以实际上是个 3\times 3 矩阵，求它的 k 次幂就可以得到答案。
时间复杂度为 O(n\log k)。
例题 12：[ZJOI 2019] 线段树
较复杂，见原题面。
将 f_i,g_i 分别设为任选一棵树中的 i 有标记的概率，以及任选一棵树的 i 至少有一个祖先（包括自己）有标记的概率，一次 modify 对五类点的转移参照前面说的。
考虑一次 modify，对于红橙绿色点的影响都可以暴力修改（它们都只有 O(\log n) 个）。
而对蓝色点则是毫无影响，不用修改。
关键是黄色点，可以发现 modify 后对其的修改就是 g_i 会变成 \dfrac{g_i+1}{2}，所以我们直接在它给的线段树结构上维护一个 g 进行了几次这样的操作的标记。
时间复杂度为 O(m\log n+n)。
最后是个小问题：求 [1,n] 的标准线段树用到的最大下标（i 的左儿子是 2\times i，右儿子是 2\times i+1，根结点是 1）。
结论如下：
ans=\begin{cases}2^{x+1}-1 \quad\quad\quad\quad\quad (n=2^x) \\
2^{x+2}-2^{x-y+1}+1\quad(n=2^x+2^y+t\quad 0\leq t<2^y<2^x)\end{cases}
证明见 Daniel13265 的博客 里的讲解，我懒得写了。
动态开点
建立 [1,n] 的标准线段树需要 O(n) 的空间，但是如果我们的操作次数 m 较小而 n 较大，那么采用动态开点的方法可以实现 O(m\log n) 的空间复杂度，但由于此时点 i 的儿子无法简单标号为 2\times i 和 2\times i+1，所以需要额外记录每个点的儿子编号。
线段树二分
考虑如下经典问题：维护一个长度为 n 的 0,1 数列，支持单点修改，以及查询左数第 k 个 1 的位置。
如果采用线段树维护这个序列，一个比较暴力的想法是在询问时二分答案 pos，求出 pos 处前缀和与 k 比较。
但是二分和线段树的 \log 是嵌套的，所以时间复杂度是 O(\log^2 n)。
考虑到线段树实际上本身就是一个分治的结构，所以可以直接在线段树的结构上进行二分。
具体地，设 Solve(l,r,k) 表示在 [l,r] 中寻找第 k 个 1，首先求 S 为 [l,mid] 的区间和，如果 S\ge k，那么说明第 k 个 1 在 [l,mid] 中，只需要 Solve(l,mid,k) 即可，否则说明第 k 个 1 在 (mid,r] 中，只需要 Solve(mid+1,r,k-S) 即可。
如此时间复杂度仅为 O(\log n)。
一般来说，线段树二分的适用范围和二分类似，需要满足单调性。
例题 13：[联合省选 2020] 冰火战士
较复杂，见原题面。
考虑到消耗总能量就是两方能量的较小值，所以我们需要使得较小值最大，并且较小值关于温度的函数是单峰（峰可以是连续一段）的，这提示我们可以用二分解决问题。
首先考虑求出能量最大值，事实上只要求出冰方能量不大于火方能量的最大温度 T，然后在 T 和 T+1 里选择一个较优值即可，而“最后一个不大于”可以转化为“第一个大于”，这是方便线段树上二分的（如果当前点之前加上 [l,mid] 仍然不大于，则答案在右边）。
然后我们需要求出使得能力最大的最高温度，这又是另一个二分，大致是求出火方总能量不小于某个值的最大温度，可以用类似的方法解决。
时间复杂度为 O(Q\log Q)。
权值线段树和 0-1 Trie
如果我们令一个线段树的下标代表的是一个值，每个结点也就代表了一段值域，那么这个线段树就叫权值线段树或值域线段树。
权值线段树可以支持一些针对值域的查询和修改操作，最经典的一类是求排名问题。
例题 14：[Luogu P3369] 普通平衡树
维护一个初始为空的可重集，支持 n 个操作，操作包括插入一个数，删除一个数，查询一个数的排名，查询排名为某个值的数，查询一个数的前驱和后继。
用权值线段树维护可重集，插入和删除即单点修改，查询排名即求前缀和。
那么如何查询排名为某个值的数呢？使用上面的线段树二分技巧，即可做到 O(\log V)。
至于前驱后继，根据题目中的定义，x 的前驱就是排名第 S(x-1) 大的，后继就是排名第 S(x)+1 大的（S(x) 是 x 处前缀和），所以这两个操作可以转化为求排名和根据排名求数。
由于值域大，可能需要使用动态开点，时间复杂度为 O(n\log V)。
例题 15：
维护一个初始为空的集合，支持 n 个操作，操作包括插入一个数，以及查询集合内所有数异或 x 后的最大值。
异或问题可以从高位开始贪心。
用权值线段树维护集合，查询时从高位到低位检查，看是否存在一个数满足更高位条件的同时当前位和 x 不同，这可以转化为查询一个区间中是否有值，容易在 O(\log V) 时间内完成。
所以时间复杂度为 O(n\log^2 V)。
然而在上面这个问题中，由于查询区间的特殊性，所以如果我们构造的是形如 [0,2^l-1] 的标准线段树，那么每个查询区间就都是线段树上一个结点了，这样的线段树就是 0-1 Trie 了。
具体地，我们构造一个高度 h（最深结点到根距离为 h）的满二叉树，每个点到左儿子和右儿子的边上分别写数字 0 和数字 1，一个叶结点对应的数字为根结点到它的路径上所有数连接形成的二进制数，此时这个 Trie 上没个点管辖的就是最高若干位确定，低位没有限制的一段值域。
因此例题 15 放在 0-1 Trie 上，时间复杂度就是 O(n\log V)。
线段树合并与分裂
考虑如下问题：有若干棵 [1,n] 的动态开点线段树，它们的总点数为 M，现有若干操作，操作为某个线段树上的查询，或将两棵线段树合并，这里的合并指的是将同一下标对应的数相加（也可以是其他形式的合并）。
设 L 表示所有线段树的叶结点总数，那么一般 L 在 \dfrac{M}{\log n} 与 M 之间，一种简单的想法是启发式合并。
每次线段树合并时我们取两棵树中叶子结点较少的一棵，然后暴力将所有叶子的信息插入另一棵，每个叶子最多被插入 \log L 次，所以复杂度是 O(L\log L\log n)。
有一种更高效，也更贴合线段树结构的合并方法。
用 ch(x,0),ch(x,1) 表示 x 的左右儿子，设函数 Merge(x,y) 表示合并 x,y 两个点表示的线段树上的子树（保证它们对应的区间一样），那么：
- 如果 x=0，则直接返回 y；
- 如果 y=0，则直接返回 x；
- 如果两个点都是叶子，直接合并信息；
- 否则，分别递归合并 Merge(ch(x,0),ch(y,0)) 和 Merge(ch(x,1),ch(y,1))，然后将 x,y 两个结点上的信息合并，返回合并后的结点。
正确性是显然的，只需要分析一下合并的总复杂度：考虑第三步递归发生的次数，由于每次发生都会将 x,y 中的一者删除，而总点数只有 M，所以这件事发生的次数不超过 M，总复杂度也就是 O(M) 了（这是指有效合并的次数，如果存在无效合并的话可能是 O(M+q)）。
此外，线段树还可以支持按某一权值分裂的功能。
在一棵（权值）线段树中，我们希望把 [1,v] 和 (v,n] 两块下标（值域）划分成两棵线段树，这时有一种很简单的 O(\log n) 算法。
考虑递归，当前递归到点 x，[v,v] 在 x 的子树中，那么：
- 首先 x 在两棵树中都要出现，我们势必要将它复制一份；
- 如果 v 恰好等于 x 左子树的右端点，那么直接将左子树分给第一棵树，右子树分给第二棵树；
- 如果 v 在左子树的更左边，那么将右子树分给第二棵树然后递归左边；
- 如果 v 在右子树，那么将左子树分给第一棵树然后递归右边。
由于线段树只有 O(\log n) 层，所以时间复杂度为 O(\log n)，同时这个操作会新增 O(\log n) 个点。
例题 16：[HEOI / TJOI 2016] 排序
维护一个 1,\ldots,n 的排列，支持 m 个操作，操作包括将一个区间中的数按升序排序或降序排序，最后查询排列在下标 q 处的值。
如果如题只要求一个位置的值，可以二分答案，转化为 0,1 序列用普通的线段树解决问题，但复杂度为 O(m\log^2 n+n)。
下面的算法不仅复杂度更优，而且能求出最终的整个序列。
这里我们采用了一点所谓“珂朵莉树”的技巧：将整个序列划分成一些有序段，用一个 set 维护所有有序段的左端点，以及这一段的顺序（递增还是递减），同时对每个有序段使用一个线段树维护其值域。
为什么要维护有序段呢？因为线段树只能用来描述区间的值域集合，而具体的排列顺序无法限定，只有确定了它递增或递减，才能知道元素的确切顺序。
排序时，我们首先将操作区间 l,r 两个端点所在的线段树分裂开，使得 l,r 分别是一段的左端点和一段的右端点，然后将这中间的所有区间进行线段树合并，表示它们并成一个大的有序段。
考虑同时合并与分裂的复杂度，注意到分裂次数为 O(n)，所以分裂的复杂度和增加的点数为 O(n\log n)，那么合并的复杂度也是 O(n\log n) 了。
此外，线段树合并还主要被用来解决一系列树上统计问题。
下面举出的例子覆盖了一些常见的应用。
例题 17：[Luogu P4556] 雨天的尾巴
给定一棵 n 个点的树，有 m 次操作，每次操作给定 x,y,z，在 x\to y 路径上所有点处放上一个 z 类物品，最后询问每个点处最多的物品种类是什么。
一个直观的想法是：建立 n 棵线段树，分别表示每个点上的物品情况。
这看似是不现实的，不过我们可以用线段树合并来将它实现。
首先将问题归为：每次在 x\to rt 路径上放一个 z 类物品，然后我们在 x 处的线段树上给 z 这个位置加上 1，然后对树进行 DFS，在此过程中每次将儿子对应的线段树合并到父亲上，然后就可以回答询问。
注意到每个点的线段树存储的实际上是自己子树内全部的标记，而因为标记只有 O(m) 个，所以复杂度为 O((n+m)\log m)。
例题 18：[PKUWC 2018] Minimax
较复杂，见原题面。
首先将所有权值离散化，然后考虑树形 DP，设权值分别为 1,\ldots,m，点 x 的权值为 v 的概率为 P(x,v)，当 x 的儿子数量小于 2 时转移平凡，否则设 y,z 为其左右儿子，那么：
P(x,v)=P(y,v)\times P(z,v)+p_x\times \Big(P(y,v)\times \sum\limits_{i=0}^{v-1}P(z,i)+P(z,v)\times \sum\limits_{i=0}^{v-1}P(y,i)\Big)+ \\
(1-p_x)\times \Big(P(y,v)\times \sum\limits_{i=v+1}^m P(z,i)+P(z,v)\times \sum\limits_{i=v+1}^m P(y,i)\Big)
考虑用线段树维护 P(x,*) 数组，我们只需要考虑线段树合并时的行为：
那么怎么维护形如 \sum\limits_{i=0}^{v-1}P(z,i) 的东西呢？
注意到我们要算的都是一棵树的前缀和或后缀和，所以在 Merge 函数中记录一下当前区间左边及右边区间的两棵树上的和即可，往左边递归时，就将后缀和加上右子树；往右边递归时，就将前缀和加上左子树。
时间复杂度为 O(n\log n)。
例题 19：[NOI 2020] 命运
给定 n 个点的有根树和 q 条祖先到后代的链，给边赋 0,1 权值使得每条链上至少有一条边权值为 1，求方案数，对 998244353 取模。
前言：
2020 年 8 月 18 日，NOI 2020 Day 1 赛场上，菜鸡 ix35 打了这题的 48 分部分分做法。
2021 年 4 月 26 日，菜鸡 ix35 做线段树合并题，并且在 30 min 切掉此题。
一年前我在 NOI 2020 的赛场上，折戟沉沙，一年后，我从倒下的地方爬起。
我成功了，我不再是以前的那个我了。
设 F(x,i) 表示以 x 为根的子树中的赋权方案，使得 x 到其深度为 i 的祖先链上至少要有一条 1 权边的方案数。
设 x 为后代的祖先链中最深的祖先深度为 d，那么初值 F(x,d)=1。
现依次加入 x 的儿子 y，通过枚举 x\to y 边是 0 还是 1，可以得到转移：
F(x,i)\leftarrow F(x,i)\times \sum\limits_{j=1}^{dep_x}F(y,j)+F(x,i)\times \sum\limits_{j=1}^{i-1} F(y,j)+F(y,i)\times \sum\limits_{j=1}^i F(x,j)
和上题套路一样，我们线段树维护 F(x,*)，Merge 时维护一下前缀和即可。
时间复杂度为 O(q+n\log n)。
例题 20：[JOISC 2021] 最悪の記者 4
给定 n 个点的内向基环树，每个点有权值 h_i，可以花费 c_i 代价修改 i 的权值为任意数，求最小的总代价，使得每个点的权值不小于它的出边指向的点。
首先考虑树的情况，设 F(x,i) 表示以 x 为根的子树中 x 的权值为 i 时的最小代价，那么：
F(x,i)=c_x\times [h_x\ne i]+\sum\limits_{y\in Son(x)}\min\limits_{j\ge i}(F(y,j))
设 G(x,*) 是 F(x,*) 的后缀 min，考虑如何从儿子的 G 得到自己的 G：
首先将所有儿子的 G 数组对应位相加，然后给所有 i\ne h_x 处的值增加 c_x，再求一遍后缀 min。
给所有 i\ne h_x 的位置增加 c_x 就相当于总答案加上 c_x，然后把 h_x 处减掉 c_x。
直接维护 G(x,*)，发现它是若干个连续段，所以我们不妨维护它的差分 G'(x,i)=G(x,i+1)-G(x,i)，就是几处点值了。
用线段树维护 G'(x,*)，先将儿子都合并起来，然后在 h_x 处加一个 -c_x，接下来考虑怎么求后缀 min：实际上这时破坏这一性质的只有 h_x 这个点，我们不断在 G'(x,*) 中找到 h_x 之前第一个非零位置，然后将那个位置与 h_x 处的值取 min 即可。
由于在整个过程中只有 n 个可能有值的点，而且一个有值的点一旦被磨平（后面的某个更小值将差分数组里这个位置改成了 0），就不会再出现，所以这个找非零位置只会找 O(n) 次。
事实上每个点维护个 set 然后启发式合并就是 O(n\log^2 n) 了，使用线段树合并可以做到 O(n\log n)。
例题 21：[JOISC 2020] 星座 3
给定 m 个二元组 (x_i,y_i)，二元组有代价 v_i，再给定序列 a_1,\ldots,a_n，求删除代价和最小的二元组集合，使得不存在两个二元组 i,j 满足 y_i,y_j>\max\limits_{k\in [\min(x_i,x_j),\max(x_i,x_j)]}(a_k)。
根据要求的特性，不难想到在序列 a_i 的笛卡尔树上处理。
设 F(x,i) 表示笛卡尔树上 x 为根的子树中保留的二元组的 y 的最大值为 i 时的最小代价，合并左右儿子 y,z（要合并 x 中区间最大值位置上的二元组也是类似的）：
F(x,i)=\min(F(y,i)+\min\limits_{j\leq v} F(z,j),F(z,i)+\min\limits_{j\leq v}F(y,j))
其中 v 是 x 代表区间的最大值。
那么这就是个简单的线段树合并了，时间复杂度为 O((n+m)\log n)。
接下来的这个问题是用线段树合并维护无向图连通块的例子。
有在线和离线两种不同的处理方式。
例题 22：[HNOI 2012] 永无乡
维护一张点带权无向图，支持连通两个点，以及查询一个点所在的连通块中第 k 大点权。
解一（在线）：
用权值线段树维护每个连通块，连通两个点时就直接进行线段树合并。
解二（离线）：
一种可能有启发意义的做法？
进行点的重标号，使得任意时刻的任意一个连通块的点标号都是连续一段区间。
如何实现呢？考虑用并查集顺便维护一个链表，每个点指向当前的后继，合并两个连通块时用其中一个的尾指向另一个的首即可。
然后就变成了求区间第 k 大，可以用主席树解决。
时间复杂度都是 O(n\log n)。
李超线段树
李超线段树可以解决如下问题：
给定 m 条不平行 y 轴的线段 l_i: y=k_ix+b_i，有 q 组询问，询问给定 x 时横坐标经过 x 处的线段中 k_ix+b_i 的最大（小）值。
为了方便，假设问题是离散的，所有询问给出的 x 都是 [1,n] 中的整数。
维护一个 [1,n] 的线段树，在线段树的每个结点 [l,r] 上维护一个“优势线段”，表示横坐标区间完全包含 [l,r] 的一条线段，要求满足：
有一种巧妙的办法来维护优势线段，考虑在点 [l,r] 上插入线段 L_1，原先的优势线段为 L_0：
- 现在要让两条线段进行 PK，不妨设在 mid 处更高的是 L_0，更低的是 L_1。
- 如果在 l,r 处都是 L_0 更高，那么 L_1 完全没用，因为整个都被 L_0 压着；
- 如果在 l 处是 L_0 更高，而 r 处是 L_1 更高，那么在 [l,mid] 中 L_1 没用，可以递归在 (mid,r] 中插入 L_1；
- 如果是 l 处 L_1 高，那么 r 处只能是 L_0 更高，与上面类似，递归在 [l,mid] 插入 L_1。
第一种情况如左图，第二种情况如右图（红线为 L_0，蓝线为 L_1）：
每次在一个完整区间中插入的复杂度是 O(\log n)，由于我们首先需要定位出 O(\log n) 个区间进行插入，所以总的复杂度是 O(\log^2 n)。
查询一次只需要将祖先链上所有直线拿出来比较，复杂度为 O(\log n)。
但要注意，如果插入的线段都可以看成直线的话（就是没有横坐标区间限制），那么插入复杂度是 O(\log n) 的。
暂时没找到什么非模板题。
可持久化线段树
如果一棵线段树在进行修改的过程中我们要维持修改前版本的线段树，那么不能对原有的结点信息直接进行修改，而需要将要修改的结点复制后修改，这就称为可持久化，可持久化线段树是最基础的一种可持久化数据结构之一。
单点修改的可持久化是简单的：原先我们只会修改一条祖先链上的所有点，现在只不过把这条链上的点全都复制一份新的。
注意可持久化线段树必然是动态开点的，并且一个点的父亲是不唯一的（进行一次可持久化操作后，复制点和原来点有一个共用的儿子）。
但当要支持区间操作时，就需要用到标记永久化的技巧。
例题 23：[SPOJ 11470] To the Moon
维护长度为 n 的可持久化序列，支持 m 次操作：区间加， 区间求和。
类似普通线段树，但修改时对于涉及到的所有结点都复制一份新的，并对应打上标记。
现在的问题是标记如何下传，答案就是不要下传，考虑到区间询问时对于某个点的区间加标记可以直接统计其贡献，而且区间加标记是可交换的，所以满足永久化条件，因此每个点的标记不动，只是在询问时算贡献。
时间复杂度为 O(n+m\log n)。
可持久化线段树可以用于一些修改后还会访问原先内容的问题中，例如上面说的树上线段树合并，如果要强制在线地询问某些信息，那么子树的线段树不能直接合并到父亲上，而需要在合并时新建结点，这也是一种可持久化。
例题 24：[CF 646 E] The Classic Problem
给定 n 个点 m 条边的有向图，第 i 条边权值为 2^{x_i}，求 s\to t 最短路，对 10^9+7 取模。
关键问题是如何维护一个点的最短路数值。
发现我们要做的有两件事：将这个值加上 2^x，以及比较两个数的大小。
分散维护显然是不现实的（总位数太大），但我们发现一个点的最短路只是在前驱的基础上加了个 2 的幂次，所以可以想到用可持久化线段树来维护每个点最短路的二进制表示。
那么加上 2^x 就简单了，找到位权为 2^{x} 的那一位之前的第一个 0，把这个 0 改成 1，然后把后面的一段 1 改成 0 即可。
再考虑如何比大小，只要比最高的不同的位即可，所以我们需要求 LCP，那自然每个区间维护一个哈希就行了。
例题 25：
总长为 n，字符集大小 |\Sigma|=10^5 的子序列自动机，AC 自动机。
子序列自动机：前一个位置的转移只是由后一个位置加上一个单点修改，只需要用可持久化线段树维护所有位置的转移即可。
AC 自动机：一个点的转移只是在其失配指针的基础上修改它有出边的儿子，也可以用可持久化线段树维护转移。
时间复杂度为 O(n\log |\Sigma|)。
可持久化线段树最常见的用法就是充当一个线段树的前缀和。
特别是权值线段树的这种前缀和化的用法，一般所说的主席树多数时候就是指这样的前缀和线段树。
具体地，用可持久化线段树依次维护序列每一个前缀的值域信息，进行区间查询 [l,r] 时用第 r 棵树减去第 l-1 棵树的信息进行查询。
一般来说主席树用于将静态在线的降维，例如区间值域查询就是将二维转成一维，这样做通常节省了一个 \log，原因是主席树本质上是前缀和，静态前缀和是线性的。
例题 26：
长度为 n 的序列，m 次询问区间颜色数，强制在线。
设 pre_i 表示 i 之前第一个和 i 颜色相同的位置。
那么查询 [l,r] 的颜色数等价于求 k\in [l,r] 的数量使得 pre_k<l（每种颜色第一次出现），也就是对于 pre 的区间值域查询，采用主席树维护。
时间复杂度为 O((n+m)\log n)。
例题 27：[CQOI 2015] 任务查询系统
有 n 个三元组 (l_i,r_i,v_i)，还有 m 个询问，询问给定 x,k，求满足 x\in [l_i,r_i] 的三元组中 v_i 的前 k 小值之和，强制在线。
一般的区间值域查询相当于贡献在单点，而询问是区间。
现在既然贡献在区间，询问是单点，不难想到差分一下，将 (l_i,r_i,v_i) 转化为在 l_i 处加入 v_i，r_i+1 处删除一个 v_i，然后查询就是前缀 [1,x] 对应的信息了。
于是又变成了区间值域查询，时间复杂度 O((n+m)\log n)。
例题 28：[FJOI 2016] 神秘数
长度为 n 的正整数序列，m 次询问不能用给定区间中若干个数的和表示的最小正整数。
这题的核心 trick 其实和主席树无关。
先求一下区间最小值，如果不是 1 那么答案就是 1；
否则，再看有没有 2，如果有 2，那么 1+2=3 以内的都能表示，再看有没有 3,4。
以此类推，设当前能表示的数的范围为 [1,pos]，我们只需要关心 pos+1 能否表示了，由于表示 pos+1 只能用到不超过它的整数，所以我们看看区间中所有不超过 pos+1 的数之和是否到达了 pos+1 即可，如果到了就更新 pos，否则答案就是 pos+1。
分析一下会跳几次，设上一次的 pos 为 pos'，那么下一次的 pos 至少为 pos+pos'（因为从 pos' 到 pos 过程中新加的必然是在 [pos'+2,pos+1] 中的数），类似斐波那契数列，显然增长是指数级的，所以跳的次数为对数级。
那么中间要用到区间值域查询，上个主席树即可。
时间复杂度为 O(m\log n\log v+n\log n)。
序列上的前缀和还可以扩展到树上的祖先和，另一种树上的扩展是将有根树展开为 DFS 序，并建立 DFS 序上的前缀和。
例题 29：
给定 n 个点的点边带权有根树，m 次询问，每次询问给定一个子树或者路径，询问 x 与其中点的点权异或最大值，或 x 与其中边的边权异或最大值。
子树点权：子树就是个区间，直接建立 DFS 序上的可持久化 0-1 Trie 进行查询。
子树边权：将边权记在较深的点上，那么边权转化成的是一个子树挖掉根结点对应的点权，还是一个 DFS 序上的区间。
路径点权：设路径 u\to v 的最浅结点为 l，它的父亲为 f，我们考虑对每个点 s 维护 s 到根的路径上所有点的点权集合 S_s，那么 u\to v 的点权集合就是 S_u+S_v-S_l-S_f，而每个点的 S_s 由父亲的加上一个数，所以可以用可持久化 0-1 Trie 维护。
路径边权：将边权记在较深的点上，同上，不过是 S_u+S_v-2\times S_l。
时间复杂度为 O((n+m)\log v)。
关于主席树功能更详细的描述可能会在数点这一部分中。
区间单调栈
考虑如下问题：维护一个序列，支持单点修改，以及查询区间 [l,r] 中前缀严格最大值的个数。
由于前缀严格最大值相当于是单调栈中的元素，所以这个问题一般就叫区间单调栈。
当然下面的算法不仅能解决这个问题，还有一些形式类似的问题也能解决。
对应线段树上的结点 p，设 s_p 表示区间内前缀最大值个数，m_p 表示区间最大值。
设 Solve(p,l,r,x) 表示求结点 p（表示区间为 [l,r]）中比 x 大的数组成的子序列中前缀最大值个数，再设 p 的左右儿子分别为 q,r。
- 如果 x\ge m_q，那么左子树不存在比 x 大的树，所以递归右边 Solve(r,mid+1,r,x)；
- 如果 x<m_q，那么在 p 中所有前缀最大值里，处于右子树的由于必定比 m_q 大，所以也一定比 x 大，一定在答案中，所以答案为 Solve(q,l,mid,x)+(s_p-s_q)。
特别注意”p 中处于右边的前缀最大值数量”并非 s_r，而是 s_p-s_q。
那么 Solve 的复杂度应当是 O(\log n) 的了（因为每次只递归一边）。
考虑如何计算 s_p，分成左右，有 s_p=s_q+Solve(r,mid+1,r,m_q)。
在 小粉兔的博客 中探讨了如何去掉 Solve 第二分类中的减号，直接令 s_p 为 p 中前缀最大值里位于右半边的即可，那么直接有 s_p=Solve(r,mid+1,r,m_q)。
分析时间复杂度：单点修改需要 O(\log n) 次 Pushup，一次 Pushup 就是一次 Solve，复杂度 O(\log n)，所以修改复杂度是 O(\log^2 n)。
而区间询问也是 O(\log n) 个区间的 Solve，所以询问复杂度也是 O(\log^2 n)。
值得注意的是，如果是全局询问，由于只有一次 Solve，所以复杂度为 O(\log n)。
例题 30：PKUSC 2021 D1T2 题目来自民间
维护一个长度为 n 的序列 a_1,\ldots,a_n，支持 m 个操作，操作包括：
- 给定 l,r，依次对每个 i\in [l,r-1] 执行 a_i\leftarrow \max(a_i,a_{i+1})；
- 给定 l,r，求 [l,r] 中所有前缀最大值之和。
一道有相当难度的数据结构题。
考虑对于每个原先的 a_i 维护一个 l_i，你可以暂时把它理解成当前序列中最靠前的一个 a_i 的位置，初始 l_i=i。
可以发现，我们不关心一个数当前前面的是不是比它大，只是将 $l_i$ 减 $1$，这样 $l_i$ 并不是我们上面说的那个意思，但目前只需要大概理解一下即可。
接下来需要一些基本的观察：
- $l_i$ 是单调不降的：容易归纳证明；
- 对于某个 $x$，设满足 $l_i\leq x$ 的最大的 $i$ 为 $y$，那么当前在 $x$ 上的数是 $[x,y]$ 的区间最大值：
首先位于 $x$ 的数的下标必定 $\ge x$，同时由于 $l_i$ 其实是某个数最左出现的一个最靠左的可能值，所以下标 $>y$ 的数肯定跑不到 $x$ 来，所以要求的数一定在 $[x,y]$ 内。
同时，这个区间最大值不可能已经不在序列中出现（否则说明有个更大的值在右侧，并且 $l$ 值不比前面那个数大，那么这才是最大值），而因为它是最大值，所以一直到 $x$ 的过程中一定畅通无阻，在此过程中它的左端点确实是每次操作都 $-1$ 的。
接下来定义删除操作：如果一次区间修改中（为避免歧义，区间设为 $[u,v]$），设 $u$ 和 $u+1$ 处目前的数分别是 $a_x,a_y$，如果 $a_x\leq a_y$ 且 $l_x=x$，那么经过这次操作 $a_x$ 就会被 $a_y$ 给吃掉（因为 $l_y\leq x$ 了，所以根据上面的结论以后 $x$ 永远消失了），我们称 $a_x$ 被删除。
接下来就是重点：
**结论：如下，设当前 $l$ 处的数为 $a_x$，而满足 $l_i\leq r$ 的最大的 $i$ 为 $y$，那么 $[l,r]$ 的区间前缀最大值集合为 $a_x,\ldots,a_y$ 中没被删除的那些的前缀最大值集合。**
证明如下：
已经被删除的数自然是没用的，我们只需要说明单调栈中没有被删除的数都还以原来的顺序存在即可。
顺序问题其实是显然的：前面已经证明了 $l_i$ 的单调性，自然不可能有一个数从前面跑到后面，而假设某个没被删除的数 $x$ 已经不存在，那只能是因为它的 $l$ 值是虚的，实际上左边有一个比它大的数卡着它，既然如此，那么它自然不会成为前缀最大值了，所以所有没被删除的前缀最大值依然存在着。
于是我们在执行修改时每次检查 $l$ 是否被删除即可，而查询的工作交给一个支持单点删除的维护区间单调栈的线段树，而单点删除相当于修改为 $0$，用我们上面说的技巧维护即可。
时间复杂度为 $O(n\log n+m\log^2 n)$。
---
#### 区间最值和历史最值
应该也属于比较复杂的势能分析。
当维护序列需要支持的操作包括将区间中的数对 $x$ 取 $\min$ 或 $\max$ 时，有一种势能分析法可以较为高效地处理。
下面叙述的是一种我比较喜欢的标记系统，也存在一些不同的实现。
考虑对于每个线段树上区间维护区间最大值 $mx$，区间最大值的个数 $cnt$，区间严格次大值 $sec$。
在递归时，假设要对 $x$ 取 $\min$：
- 若 $mx\leq x$，则本次操作对该区间无效，直接返回；
- 若 $sec<x<mx$，则本次操作只改变最大值的值，把 $mx$ 改为 $x$ 并更改相关的信息。
- 若 $x\leq sec$，则继续递归。
若只有这一种修改操作，时间复杂度为 $O((n+m)\log n)$，如果还有区间加这样的操作，那么复杂度会变成 $O(n\log n+m\log^2 n)$，证明有空再来写。
考虑如果同时出现区间最值操作和区间加操作，由于区间最值操作的标记只会对区间最大值产生影响，所以我们维护两套标记，一套负责最大值，一套负责非最大值，就可以处理好两种操作的关系。
---
另一类问题是求历史最值，也就是询问某个区间 $[l,r]$ 曾经的所有最值的最值。
这个问题和势能分析并没有关系，考虑最简单的情形：区间加，区间求历史最值。
我们维护两个标记 $ad1,ad2$ 分别表示当前区间的加法标记以及**区间历史最大值的加法标记**，同时维护 $mx1,mx2$ 表示区间最大值和区间历史最大值。
现在考虑在点 $p$ 上加上 $x$ 的区间加法标记以及 $y$ 的区间历史最大值标记，造成的影响如下：
- $ad1\leftarrow ad1+x,\ mx1\leftarrow mx1+x$，这和不算历史最大值的情况一样；
- $ad2\leftarrow \max(ad2,ad1+y),\ mx2\leftarrow \max(mx2,mx1+y)$，考虑后一个式子的意义：如果当前的值加上之前没传下来的最大标记应该超过了原先历史最大值，那么就要更先历史最大值，同时标记当然也要进行等量的修改。
考虑下传标记的逻辑关系：$p$ 原本的 $mx2$ 表示不计算父亲的标记时的历史最大值，而算上父亲标记时，每个时刻的最大值都是 $mx2$ 加上当时父亲的加法标记 $x$，而所有这些 $x$ 的最大值就是 $y$，而这些 $x$ 都作用在操作之前的“当前最大值” $mx1$ 上，所以是 $mx1+y$。
时间复杂度为 $O(n+m\log n)$。
---
一些扩展：
你来到了一片没有知识的荒原。
---
> 例题 $31$：[UR #19] 前进四
>
> 维护长度为 $n$ 的序列，支持 $m$ 个操作，操作包括单点修改，以及询问某个后缀中后缀严格最小值的个数。
>
> 可以离线，$O(n+m\log n)$。
利用我们前面说的区间单调栈，可以直接得到一个 $O(n\log n+m\log^2 n)$ 的在线做法，但是这不够优。
而使用区间最值操作可以巧妙地得到本题的一个离线算法。
考虑离线后倒序扫描，假设当前扫到 $x$，建立以时间为轴的线段树维护每个时刻 $[x,n]$ 的后缀最小值以及这个后缀的后缀最小值个数。
考虑加入 $x-1$ 的一个修改操作（修改为 $v$），假设该操作生效的时间区间为 $[l,r]$，那么相当于在线段树上 $[l,r]$ 内所有点对应的后缀最小值与 $v$ 取 $\min$，并且如果 $v$ 更小，就要把答案 $+1$。
利用一个支持区间最值操作的势能分析线段树即可完成。
由于只有区间取 $\min$ 一种修改操作，因此时间复杂度为 $O(n+m\log n)$。
---
> 例题 $32$：[Ynoi 2009] rprmq
>
> 有一初始全 $0$ 的 $n\times n$ 矩阵，首先进行 $m$ 次矩形区域加操作，然后 $q$ 次询问矩形区域最大值。
>
> $O(m\log n\log m+q\log n)$。
离线的两维问题是假两维，将行作为时间轴，转化为序列问题。
现在问题相当于：依次进行若干次区间加操作，并 $q$ 次询问一个区间在一个时间范围内的最值。
如果每次询问的矩形都顶着上边界，相当于每次都是问一个前缀时间的最值，按时间离线后是什么呢？就是一个区间历史最值了。
这启发我们将类似的方法从前缀移植到区间上，而专职用来干这个事情的就是序列分治：
考虑取时间中点 $mid$，当前递归的时间区间为 $[L,R]$，考虑一个跨过 $mid$ 的询问，时间区间为 $[l,r]\ (L\leq l\leq mid\leq r\leq R)$，可以将问题分成两个：求 $[l,mid]$ 的历史最值，和 $(mid,r]$ 的历史最值。
这两个都可以看成前缀询问：我们先做 $[L,mid]$ 中的所有操作，不保存历史最值（就是说这过程中的任意操作都不计入历史最值），然后再做 $(mid,R]$ 中的操作，此时保存历史最值，然后按时间离线后询问到的就是 $(mid,r]$ 中的历史最值了。
每个操作会在 $\log m$ 层中都出现，但询问只有一次，我们用修改上多一个 $\log m$ 的代价换了询问的一个 $\log n$。
时间复杂度为 $O(m\log n\log m+q\log n)$。
---
根据上面两个例题，我们可以总结：许多时候区间最值和历史最值的区间这一维下标对应的是时间轴，这要求我们在大部分情况下要先离线后才能处理。
---
### 树状数组
取出 $[1,2^n]$ 标准线段树中所有左儿子和根，构成一个森林结构，就是**树状数组**。
树状数组也称**芬威克树**（Fenwick Tree），**二叉索引树**（Binary Index Tree）。
树状数组相比于线段树的优点在于有着更小的时间和空间常数（具体地，少了一半），易于储存，但缺点是只能维护前缀的可结合信息——从结构来看，它是一个只能支持前缀区间定位的线段树。
设 $\operatorname{lowbit}(x)$ 表示 $x$ 二进制下最低位的 $1$ 的位权，考虑一个 $[1,n]$ 的树状数组，结点 $i$ 维护的是区间 $[i-\operatorname{lowbit}(i)+1,i]$ 的信息，查询前缀 $[1,x]$ 的信息时，我们只需进行一个简单的循环：初始令 $s=x$，然后不断累计 $s$ 的信息，然后令 $s\leftarrow s-\operatorname{lowbit}(s)$，直到 $s=0$。
正确性显然，而复杂度证明也很简单：只会循环 $s$ 在二进制下 $1$ 的个数次。
树状数组也可以支持动态开点，但一般来说这样做就影响了它的便捷性，所以一般要么用线段树替代，要么进行离散化。
树状数组大部分时候可以被线段树替代，基本只用于一些比较简单的序列维护问题以及动态二维数点的外层树。
---
### K-Dimensional Tree
线段树维护了 $[1,n]$ 中的一个树形的线段集合，使得任意一条指定线段都可以拆成其中 $O(\log n)$ 个线段的不交并。
将这个问题扩展到更高维，我们需要一种数据结构，维护 $[1,n_1]\times [1,n_2]\times\ldots\times [1,n_k]$ 中的一个超长方体集合，使得任意一个给定的超长方体都可以拆成其中数量较少的超长方体的不交并。
可惜的是，要彻底做到这一点很难，我们退而求其次，解决下列问题：
给定 $m$ 个 $[1,n_1]\times [1,n_2]\times\ldots\times [1,n_k]$ 中的点，我们需要用一种数据结构维护一些点集，使得任意给定一个超长方体，其中包含的点都可以由较少的点集的不交并得到。
KD-Tree 解决这个问题的方法基于对点集的划分：
建立一个二叉树，每个结点维护一个超长方体内的点，假设当前点集为 $S$，若 $|S|\ne 1$，则挑选一个维度 $i$，按第 $i$ 个维度将所有点排序，设前一半和后一半分别为 $S_0,S_1$，分别递归构造 $S_0,S_1$ 的子树，令它们为 $S$ 对应结点的左右儿子。
那么如何选切分维度就比较关键，有一种比较简单的方法：第 $i$ 层划分时就划分第 $(i-1)\bmod k+1$ 维，也就是轮流划分。
KD-Tree 建树复杂度为 $O(n\log n)$，因为求长为 $n$ 的序列中的第 $k$ 大可以 $O(n)$ 完成。
下面分析这种 KD-Tree 进行一次超长方体定位的复杂度。
KD-Tree 的定位原理和线段树一样，考虑 $k$ 维超长方体中包含的 $2k$ 个 $k-1$ 维超长方体表面，我们求出这其中每个超平面经过的点集数量，再相加，就与复杂度直接相关。
考虑一个超平面，在连续 $k$ 轮划分中，原本的点集被分为了 $2^k$ 个子点集，而超平面必然只能经过其中最多 $2^{k-1}$ 个（可以选超平面少掉的那一维用扫描线进行分析），再递归下去，所以设点集大小为 $n$，复杂度是：
$$T(n)=2^{k-1}T(\dfrac{n}{2^k})+O(2^k)$$
这里讨论 $k$ 较小的情况，$O(2^k)$ 可以看成常数 $C$，对 $n$ 应用 Master 定理，分类讨论：
- 如果 $\log_{2^k} 2^{k-1}=\dfrac{k-1}{k}=0$，那么 $k=1$，此时时间复杂度为 $O(n\log n)$，这就是线段树的复杂度。
- 如果 $\log_{2^k} 2^{k-1}=\dfrac{k-1}{k}>0$，那么 $k>1$，此时时间复杂度为 $O(n^{1-\frac{1}{k}})$。
由于总共 $O(k)$ 个超平面，所以第二类应该实际上是 $O(k\times n^{1-\frac{1}{k}})$。
例如，$k=2$ 时的 KD-Tree，一条边线最多经过一个点集分治两层后四个点集中的两个，如图，复杂度为 $O(\sqrt n)$。
实际上你可能已经注意到，上面叙述的 KD-Tree 大致是一种类似线段树的结构，最后的叶子是每个点，这种结构被称为是 Leafy 的，而另一种比较广泛使用的 KD-Tree 采用的是类似 BST 的结构，每个结点都存储一个单独的点，一般来说 Leafy 的数据结构好维护些。
---
> 例题 $33$：
> 维护一个二维平面上的大小为 $n$ 的点集，支持 $m$ 个操作，操作包括矩形区域加，以及矩形区域求最值。
直接上 KD-Tree 的矩形拆分即可。
时间复杂度为 $O(n\log n+m\sqrt n)$。
---
带插入的 KD-Tree：
如果强制在线问题中要求往 KD-Tree 中加点，最常见的解决方法是设置平衡常数 $\alpha$，插入后一旦某个最浅的祖先满足某个儿子的比重超过 $\alpha$ 就暴力重构，复杂度我不会分析。
还有一种复杂度容易分析的做法，根号重构：每插入 $B$ 个点就重新建 KD-Tree，而最近一块中的点在查询时可以暴力访问。
由于一次重构复杂度为 $O(n\log n)$，而查询复杂度为块长加上 $O(\sqrt n)$，所以当操作数为 $m=n$ 时可以设定 $B=\sqrt{n\log n}$，得到总复杂度 $O(n\sqrt{n\log n})$。
---
KD-Tree 实现搜索剪枝
在很多 $k$ 维空间搜索问题中，采用 KD-Tree 的递归结构可以进行大量最优性剪枝，从而达到期望较优的复杂度。
最常见的问题就是最近 $k$ 点问题。
注意 KD-Tree 的复杂度只有超长方体查询时才有确定的保证。
---
> 例题 $34$：[BZOJ 3053] The Closest M Points
> 给定 $k$ 维空间中 $n$ 个点，$q$ 次查询与给定点欧几里得距离前 $m$ 小的点。
采用非 Leafy 的结构，在 KD-Tree 上 DFS，用一个堆维护当前的前 $m$ 小答案。
定义一个点到 KD-Tree 上一个结点的距离 $dis$：设这个结点子树内所有点形成的最小超长方体为 $[l_1,r_1]\times\ldots[l_k,r_k]$，即 $l,r$ 分别是每一维坐标的最小值和最大值，$dis$ 就是点到这个超长方体的最短距离。
DFS 到一个结点时，假设询问点到当前结点距离超过堆中最大值，那么直接剪枝，不用递归。
否则，先尝试加入根代表的点（如果比堆中最大值小就替换），然后递归左右儿子。
时间复杂度玄学（最差应该是 $O(nq\log m)$），当给定点平均分布在以询问点为球心的超球面附近时表现较差。
---
用 KD-Tree 解决一些二维平面上的矩形划分问题，可以实现一些两层树套树做不到的功能，但代价是 $n$ 的指数增加 $0.5$。
---
## 2. 基本思想
因为快要 NOI 了，所以我之后写的可能有点暴躁，有可能会越写越短，毕竟本来是写给自己看的。
这一部分会提到一些数据结构以及其他算法中常用到的思路，比如序列分治，cdq 分治，整体二分，莫队，简单的分块等。
### 序列分治/猫树
实际上这个思路在前面那个 ynoi 题里就说到了，首先考虑一个简单的题目：
---
> 例题 $35$：
>
> 给定长度为 $n$ 的序列，$q$ 次询问区间和/区间最值/区间 $\gcd$/区间最大子段和。
解一：
线段树，都可以线段树。
时间复杂度 $O(n+q\log n)$。
解二：
区间和可以前缀和做到 $O(n+q)$，区间最值和区间 $\gcd$ 可以 ST 表做到 $O(n\log n+q)$。
那么，最大子段和上，难道不能去掉 $q$ 乘的 $\log n$ 吗？
当然可以，我们考虑对序列进行分治，假设当前处理所有询问区间属于 $[l,r]$ 的询问，设 $mid=\dfrac{l+r}{2}$。
对于每个 $i$ 维护 $[i,mid]$（如果 $i\in [l,mid]$）或 $[mid+1,i]$（如果 $i\in [mid+1,r]$）的最大前缀和，最大后缀和，最大子段和，然后对于跨过 $mid$ 的询问，我们可以 $O(1)$ 得到答案（用前后缀拼一下）。
那么不跨过 $mid$ 的询问自然可以递归成 $[l,mid]$ 和 $[mid+1,r]$ 分别求解。
这样询问的复杂度降到了 $O(1)$，总复杂度 $O(n\log n+q)$。
---
具体怎样的问题可以直接用这个方法求解：
1. 没有修改；
2. 可以给每个区间维护信息，使得一个区间的答案可以由前后缀的信息拼合；
3. 在区间头或尾新增元素，信息可合并。
可能讲的不太本质。
---
但是上面这个做法还有个问题：它是离线的。
我们可以通过一系列操作将它在线化，具体就是记录下分治的整个过程。
考虑建立 $[1,n]$ 的线段树，对于每个区间 $[l,r]$，对所有 $i\in [l,r]$ 记录 $[i,mid]$ 或 $[mid+1,i]$ 的区间信息。
然后对于询问 $[l_0,r_0]$，我们只需要找到线段树上 $[l_0,l_0]$ 和 $[r_0,r_0]$ 的 LCA，然后根据这个点上 $l_0,r_0$ 的信息来 $O(1)$ 回答询问。
问题就是如何找这个 LCA？显然用 ST 表有经典的 $O(n\log n)-O(1)$ 做法。
考虑到线段树 $O(\log n)$ 层，每层每个点都有个到它所在区间分治中心的信息，所以时空复杂度本身就是 $O(n\log n)$，求 LCA 不会增加复杂度。
所以这样的话总的复杂度就是 $O(n\log n+q)$，可以支持在线区间询问，但不能修改。
值得一提的是，如果 $n=2^k$，上面求 LCA 还可以再简单一些——直接求 $l_0\oplus r_0$ 的最高位 $1$，就得到了 LCA 的深度，而分析上述过程发现我们并不需要 LCA 具体是哪个点，知道深度就够了。
上面的这种线段树似乎就叫**猫树**。
---
> 例题 $36$：[Luogu P7482] 不条理狂诗曲
>
> 给定 $n$ 个点的点带权链，求所有区间（一条子链为一个区间）点权最大独立集之和。
考虑序列分治，设当前分治区间 $[l,r]$，分治中心 $mid$，对于 $i\in [l,mid]$ 预处理 $a_i$ 表示 $[i,mid]$ 最大点权独立集，$b_i$ 表示 $[i,mid-1]$ 最大点权独立集，同理对于 $i\in [mid+1,r]$ 预处理 $c_i$ 表示 $[mid+1,i]$ 最大点权独立集，$d_i$ 表示 $[mid+2,i]$ 最大点权独立集。
设 $f(l_0,r_0)$ 为区间 $[l_0,r_0]\ (l\leq l_0\leq mid< r_0\leq r)$ 最大点权独立集，那么有：$f(l_0,r_0)=\max(a_{l_0}+d_{r_0},b_{l_0}+c_{r_0})$。
考虑何时取到前者，即 $a_{l_0}+d_{r_0}\ge b_{l_0}+c_{r_0}$，所以 $a_{l_0}-b_{l_0}\ge c_{r_0}-d_{r_0}$。
所以我们将左右边点按照 $a-b$ 和 $c-d$ 排序，枚举左边点，对于 $c-d$ 不超过当前点 $a-b$ 的都取 $a+d$ 为答案，否则取 $b+c$ 为答案，这容易通过维护 $c,d$ 的部分和来实现。
时间复杂度为 $O(n\log^2 n)$（考虑到需要排序，而且这里元素会变，不可以归并）。
---
> 例题 $37$：[COCI 2015] Norma
>
> 给定长度为 $n$ 的序列，定义一个区间的权值为区间最小值乘区间最大值乘区间长度，求所有区间权值和。
序列分治，设当前分治区间 $[l,r]$，分治中心 $mid$。
枚举 $i\in [l,mid]$，设 $a,b$ 为 $[i,mid]$ 的最小值和最大值，再令 $u,v$ 分别表示 $[mid+1,r]$ 中一个最小的数，使得其到 $mid+1$ 的区间中最小值小于 $a$，或最大值大于 $b$。
那么 $u,v$ 就把 $[mid+1,r]$ 分成了三段，每一段分别可以通过一些部分和简单地算出答案，这里不列式子了。
时间复杂度为 $O(n\log n)$。
---
> 例题 $38$：
>
> 给定平面上 $n$ 个点，求欧几里得距离最近点对。
其实和数据结构没什么关系，但是也是分治。
设 $n$ 个点为 $p_1,\ldots,p_n$，不妨设它们横坐标递增，令 $A(l,r)$ 表示 $p_l,\ldots,p_r$ 中的最近点对距离（$r-l\ge 1$）。
考虑如何求 $A(l,r)$，首先分治，令 $A_0=\min(A(l,mid),A(mid+1,r))$，我们只需要考虑是否存在 $l\leq u\leq mid<v\leq r$ 使得 $p_u,p_v$ 的距离 $d(u,v)$ 小于 $A_0$。
我们只取中点所在横坐标两侧 $A_0$ 范围内的点（如图左右两条线之间），枚举一个左侧点 $p_i$，然后只考虑纵坐标与其差不超过 $A_0$ 的点，由于右侧任意两点距离不小于 $A_0$，所以根据简单的抽屉原理可知这样的点最多有六个（如图中六个红点），所以依次枚举是可以接受的。
我们只需要将左右两边的点分别按照纵坐标排序，枚举左边点，对右边点按照纵坐标双指针，然后每次对区间中所有合法右侧点枚举一遍更新答案即可。
时间复杂度 $O(n\log n)$。
---
还有一类分治由于涉及到区间最值，常会取最值点作为分治点。
但此时破坏了 $\log$ 层的结构，所以一般会涉及到启发式合并等技巧。
其实这种分治也可以看作笛卡尔树上的搜索。
---
> 例题 $39$：[Luogu P4755] Beautiful Pair
>
> 给定长度为 $n$ 的序列 $a_1,\ldots,a_n$，求有多少个区间 $[l,r]$ 满足，$a_l\times a_r\leq \max(a_l,\ldots,a_r)$。
分治到区间 $[l,r]$ 时，设 $a_p$ 是 $[l,r]$ 的区间最大值，考虑跨过 $p$ 的区间，最大值一定是 $a_p$。
也就是说，我们要在 $[l,p-1],p,[p+1,r]$ 中任选两段各拿出一个数，积不超过 $a_p$ 的方案数。
用线段树维护当前做完的区间（如 $[l,p-1]$ 和 $[p+1,r]$），然后采用启发式合并，每次选其中长度短的那一边枚举，更新答案并将所有值插入另一棵线段树中。
时间复杂度为 $O(n\log^2 n)$。
---
### CDQ 分治
cdq 分治其实有很多应用场景，比如决策单调性 DP 的分治优化，分治 FFT 等都是 cdq 分治的思想，但这里主要说的是和数据结构关系比较大的。
先从最简单的说起：归并排序求逆序对。
采用一个分治的思想，如果我们先将左右分别排序，然后仅考虑一左一右构成的逆序对。
那么原本两维的问题（位置，大小）就变成了一维（大小），分别排序后扫一遍即可。
同时排序也就简单了，可以 $O(n)$ 合并两个长度为 $n$ 的有序数组。
所以说，在一些数点问题中，CDQ 分治可以以一个 $\log$ 的代价，使问题的维度降低 $1$。
---
### 数点
许多数据结构问题最后都化为数点问题。
最经典的数点问题形如：给定 $n$ 个 $k$ 维空间中的点，$q$ 次询问超长方体中的点数。
根据是否在线，是否有修改要求等，可以继续分成一些 Case。
---
衡量一个数点算法，主要看它的**预处理时间复杂度**，**单次询问时间复杂度**以及**空间复杂度**。
我们有许多工具，设第 $i$ 个维度坐标大小范围为 $D_i$，首先来回顾一下：
| 工具 | 预处理复杂度 | 询问复杂度 | 空间复杂度 | 适用范围 |
| :----------------: | :-------------------: | :----------------: | :-------------------: | :----------: |
| 前缀和 | $+O(\prod D_i)$ | $\times O(1)$ | $+O(\prod D_i)$ | 静态，在线 |
| 线段树（树状数组） | $(n)\times O(\log n)$ | $\times O(\log n)$ | $(n)\times O(\log n)$ | 带修改，在线 |
| CDQ 分治 | $(n)\times O(\log n)$ | / | $(n)\times O(1)$ | 离线 |
CDQ 分治没有询问复杂度是因为它是离线算法，预处理复杂度就表示总的复杂度。
上面这个表可能不是很严谨，但可以稍微理解一下。
此外，我们可以用**扫描线**将静态离线问题降 $1$ 维变成动态问题，也可以主动将动态问题升 $1$ 维变成静态问题。
稍微总结一下：
1. 每个询问的复杂度由 CDQ 分治和树套树的总层数相加决定；
2. 每用一层前缀和，这一部分预处理时空复杂度乘上 $O(D_i)$，所以一般前缀和最多用一层；
3. 空间复杂度由树套树的层数决定。
---
#### P1：在线/离线静态一维数点
$O(D_1)$ 可以接受时采用前缀和，复杂度 $O(D_1+n+q)$。
否则要用前缀和就要离散化，是 $O((n+q)\log n)$。
离线情况下的处理可以理解成扫描线，但因为要排序所有有个 $\log n$。
---
#### P2：在线动态一维数点
使用线段树，$O(n\log n)-O(\log n)$。
---
#### P3：离线静态二维数点（离线动态一维数点）
扫描线+树，$O(n\log n)-O(\log n)$。
也可以 CDQ+扫描线，$O(n)-O(\log n)$。
---
#### P4：在线静态二维数点
前缀和+树（也就是主席树），$O(n\log n)-O(\log n)$。
---
#### P5：在线动态二维数点
由于在线且动态，前缀和和扫描线这样 $O(1)$ 的白嫖工具都失效了。
老老实实采用树套树，$O(n\log^2 n)-O(\log^2 n)$。
---
#### P6：离线静态三维数点（离线动态二维数点）
扫描线+树+树，空间 $O(n\log^2 n)$。
CDQ+扫描线+树，空间 $O(n\log n)$（去看陌上花开题解，最常见的方法）。
CDQ+CDQ+扫描线，空间 $O(n)$。
时间是 $O(n\log^2 n)$，当然是 $n,q$ 同阶的情况下（否则还要看看 $\log$ 在哪）。
---
再套下去感觉意义不大了，反正这种常规问题的一般套路就是：
如果静态，可以将一维用扫描线（排序即扫描线）或前缀和（如果在线）处理掉。
之后根据离线或在线考虑用 CDQ 或树来解决。
大家似乎比较喜欢在离线问题中使用恰好一层树。
---
当然，如果问题稍微修改一下：比如超长方体区域最大值，这时 CDQ 分治和前缀和等基于差分的方法可能会失效，考虑采用树套树解决。
此外，直接使用 KD-Tree，将复杂度加在 $n$ 的指数上，也是一种可以考虑的方案。
---
#### K 维偏序
一类比较特殊的数点问题：给定 $n$ 个 $k$ 维空间点 $P_1,\ldots,P_n$，求二元组 $(i,j)$ 的个数使得 $P_i$ 各维坐标均不大于/小于 $P_j$ 的各维坐标。
发现这个问题可以暴力，复杂度为 $O(kn^2)$。
发现这个问题可以看作离线静态 $k$ 维数点，复杂度为 $O(n\log^{k-1} n)$。
发现数点也可以用 KD-Tree，复杂度为 $O(k^2\times n^{2-1/k})$（存疑）。
还有一种比较诡异的暴力优化，考虑维护矩阵 $M_i\ (i\in [1,k])$ 表示第 $i$ 维某两个点的大小情况（$P_x$ 比 $P_y$ 小则第 $x$ 行 $y$ 列为 $1$，否则为 $0$），然后把所有 $M_i$ 对应位置相乘后取 $1$ 的个数即可。
可以发现这可以用 bitset 维护，求矩阵可以对每一维排序后分开考虑，复杂度 $O(kn\log n+\dfrac{kn^2}{\omega})$。
有的时候时间可以但是空间开不下，这时候可以使用分块优化空间，后面再说。
---