8
前言
本文篇幅较长，里面包含了对线段树进阶用法的介绍和本人对此的理解，希望这篇文章能帮助你更好的掌握这些知识。(ps: 请你保证至少会基础线段树以及简单用法)
Update: 于 2025年8月1日完成动态开点还有部分可持久化线段树。
Update: 于 2025年8月20日完成可持久化线段树进阶内容。
线段树动态开点
一般而言，线段树是一颗完全二叉树。但是有些题目需要我们维护较大的值域信息，这时候一般的建树方法并不适用，所以我们需要使用动态开点的方法。
回顾线段树基本原理，在值域极大的情况下，线段树在查询或修改时有些节点我们可能从始至终都不会用到，此时就没有必要把这样的节点保存。换句话说，我们按需分配，只保存需要访问的节点，这样就可以做到合适的复杂度了。注意，此时就不能直接建树了，更不能使用堆式存储法（因为我们的节点是动态储存的）。
实现有两种主流方法：第一，用取地址符更新节点。第二，直接函数返回编号。个人更倾向于好写简洁的第一种方法。
上面列举的是单点修改的做法，我们可以把这个过程理解为向线段树添加若干条链，查询时就在这颗稀疏二叉树上正常访问即可。
对于区间修改而言，下传懒标记时我们需要判断左右儿子是否存在，如果不存在需要新建。(注意这里的空间开销不小)
当值域远大于操作规模时我们的空间复杂度大概是 O(nlogV)O(n \log V)O(nlogV) 的，时间复杂度同理，但是需要注意的一点是区间修改下传标记所需要的额外开销，一般需要开 303030 到 505050 倍不等，建议在不超过空间限制的情况下尽量将数组开大一些以保证正确性。
这里附送一道例题，需要支持区间修改和区间查询：CF915E Physical Education Lessons
可持久化线段树
前置知识：动态开点线段树.
该部分篇幅较长，请读者根据需求自行选择阅读。
持久化数据结构基础介绍
> " 可持久化数据结构 (Persistent data structure) 总是可以保留每一个历史版本，并且支持操作的不可变特性 (immutable)。 ----- 摘自 OIwiki
在很多题目中，我们可以通过离线思想配合扫描线等算法批量处理问题，以达到优化复杂度的目的。但有些题目需要我们处理在线操作，这时就需要可持久化数据结构了。
所谓可持久化数据结构，就是支持对维护信息的历史版本做查询和修改的数据结构。我们对可持久化数据结构的操作自由度将其分为四类：
* 部分可持久化：可以访问所有版本，但是只支持修改最新版本。
* 完全可持久化：所有版本都可以访问修改。
* 可合并可持久化：在完全可持久化的基础上，支持将两个历史版本合并。
* 函数式可持久化：函数式编程中实现的持久化数据结构，对象都是只读的，任意修改都是创建一个新的节点，而不是在旧节点上修改。
以上四种持久化是逐步增强的，后者包含于前者。在算法竞赛中，我们一般只在意前两种可持久化结构。
简介和说明
可持久化线段树，又被称之为主席树，由 NOI 选手黄嘉泰（HJT）发明。（有个有趣的说法，称其发明原因是发明者当时不会写划分树，从而用此结构替代)
而很多地方也称主席树为可持久化权值线段树，这些叫法五花八门，初学者需要理清这些概念，避免混淆，这里均使用全名可持久化线段树。
原理实现
首先我们先介绍一下权值线段树，就是对于一个固定的序列维护一颗线段树，每个数按其权值为下标插入线段树中并维护值域信息。容易发现，我们可以通过线段树二分的方式做到 O(logn)O(\log n)O(logn) 的时间求全局第 kkk 大。
由此，我们引出一道经典题目：给定由 nnn 个正整数构成的序列 aaa，对于指定的闭区间 [l,r][l, r][l,r] 查询其区间内的第 kkk 小值。
首先，我们假设对区间 [l,r][l,r][l,r] 内的树构造一颗值域线段树，那么问题就转化为了全局第 kkk 大。我们发现，实际上每个数的出现次数可以差分处理。比如说我们需要计算 [l,r][l,r][l,r] 内数 xxx 的出现次数，就可以通过 [1,r][1,r][1,r] 中 xxx 的出现次数减去 [1,l−1][1,l-1][1,l−1] 中 xxx 出现的次数得到答案。
也就是说，我们可以参考前缀和的思想维护 nnn 棵值域线段树，第 iii 棵线段树维护区间 [1,i][1,i][1,i] 内的桶信息，查询时就可以通过对第 rrr 棵线段树和 l−1l-1l−1 棵线段树作差得到区间上线段树的实际信息。
至于如何维护这 nnn 棵线段树，其实也不是一件麻烦事。沿用上文线段树动态开点的思想，容易发现第 iii 棵线段树的维护信息与第 i−1i-1i−1 棵线段树仅有一个数 aia_iai 之差，换到线段树上只是多了一条长度为 logn\log nlogn 的链而已。故用一个数组 rtrtrt 记录每个线段树的根，记录左右儿子的基础上动态开点就可以了。
这里引用了 OIwiki 里的例子，下图表现了修改 [1,8][1,8][1,8] 中 111 的例子：
注意，我们实际上每次插入是直接新建节点的，与之前这个节点是否出现过无关。实际上，可持久化线段树形成的结构严格来说并不是一棵树，因为一个节点可能被多个父节点引用，但这并不影响我们查询信息。
插入的具体实现也是较为简单的，类似动态开点的技巧我们每次新建一个节点，再把前驱节点的信息复制给它，并对信息做相应的更新。
在值域不大的时候我们可以先建一颗空树，然后再像上图一样依次插入，就避免了空节点无法复用的麻烦。如果避免不了值域大的问题，我们就只能参考动态开点的方式每次新建节点。
事实上，由于线段树的树高在 logn\log nlogn 量级，所以每插入一个数我们所需要的空间是 O(logn)O(\log n)O(logn) 左右，这意味着一颗可持久化线段树所需空间是 O(nlogn)O(n \log n)O(nlogn) 量级的。
下面给出【模板】可持久化线段树 2 基于可持久化线段树的实现：
实际上很多可持久化线段树问题的空间限制非常宽松，我们完全可以和实现动态开点线段树时一样在不超空间的限制下尽可能多开线段树节点。
进阶用法
可持久化线段树实际上也有很多扩展用法，比如差分统计信息或处理偏序问题，建议读者在掌握其基础用法后再阅读本部分。
配合树上差分
在序列上查询信息我们可以通过差分达到目的，在树上我们可以通过树上差分的方式解决问题。
比如说这道题：P2633 Count on a tree，要求我们在线回答树上路径第 kkk 小。
考虑树上差分的方式，我们用第 iii 颗线段树表示根节点 111 到 iii 路径上所有点的信息。类似序列上的做法在深度优先搜索的时候顺便维护即可，查询时用树上差分的技巧维护链信息即可。
区间修改
这部分可能会有些难以理解，请读者先掌握基本用法。
很多人初学主席树可能会有一个误区：它不支持区间修改还有区间查询。这个想法我可以很明确的告诉你：它大错特错。现在我们来通过解决一道数据结构题来展开讲解。
首先我们先不考虑可持久化的问题，发现实际上加操作是很好维护的，但推平操作很难维护。所以在这里我们有一个重要观察: m≤4m \le 4m≤4，这意味着可以支持对行状态压缩。
我们设 fS,j=∑i∈SAi,jf_{S,j} = \sum_{i \in S} A_{i,j}fS,j =∑i∈S Ai,j 。令满状态 p=2m−1p = 2^m-1p=2m−1，那么我们只需要在意 fp,jf_{p,j}fp,j 。只有一行的区间推平操作是好维护的，我们只需要在下传标记的同时更新所有与操作行相关的状态 SSS 即可。比如说我要把第 iii 行某个区间修改成 xxx(这里从 000 开始标号)，对于区间内所有满足 i∈Si \in Si∈S 的状态，我们直接让 fS,j=fS−i,j+xf_{S,j} = f_{S-i,j} + xfS,j =fS−i,j
+x。注意这里我们需要从小到大依次更新，并且只需要更新对应的状态。
将上述更新方法沿用至线段树上，我们就做到了用 2m−12^m-12m−1 颗线段树维护推平操作了，至于加操作是同理的，我们只需要处理所有有关的状态对应的线段树。这里建议开一颗线段树，然后维护 2m−12^m-12m−1 个状态，或许会好写一点。
这里提供下传标记的代码：
我们回到可持久化的问题，类比单点修改，区间修改实际上也是在一个版本基础上进行节点信息复制。对需要访问的节点新建版本，否则直接继承版本基础的节点。
然后考虑下传标记的问题，由于我们并不知道每个节点的对应的版本，所以每次我们都需要新建节点，读者可以观察上述代码中 down 函数的第一行。
也就是说，我们在每次区间修改时对访问节点新建，下传标记时新建节点。这样就做到了维护区间修改还有区间查询的问题了，打破了其仅能通过差分进行区间查询的局限性。
这里提供此题的参考代码（std）。若对解决此题感兴趣，可私信作者获取题目或测试数据。
很多题目没有让可持久化线段树支持区间修改与查询的原因在于巨大的空间开销，同时这里依然建议多开节点保证正确性。
线段树合并
前置知识：权值线段树，动态开点线段树。
该内容比较简单，读者可以只是稍作了解。
简介和说明如果没有特殊说明，这里默认 nnn 和值域 VVV 同阶。
一般而言，权值线段树的操作空间实际上是很小的，因为它只支持修改某些数的出现次数，遇到一些复杂度操作就不行了，比如可重集合并类似的操作。这时候我们就需要引入线段树合并这一概念了。
原理实现
事实上合并两个集合我们有一个非常公式化的做法：启发式合并。只需要每次把较小的集合元素全部加入到另一个集合当中，这样发现对于每个较小集合元素，所在新集合大小至少为原来的两倍，所以一个元素至多被加入 O(logn)O(\log n)O(logn).权值线段树套用启发式合并的方法可以做到 O(nlog2n)O(n \log^2 n)O(nlog2n)。
但事实上这个复杂度并不优秀，如果我们能够快速的维护两个节点内合并的信息那就可以使用线段树合并的技巧做到 O(nlogn)O(n\log n)O(nlogn)。
线段树合并的过程实际上非常简单，大概率你能直接推导出如何合并。
假设有两个需要合并的线段树 A 和 线段树 B（其中我们把线段树 B 的信息插入至线段树 A），我们考虑同时递归搜索这两棵树并讨论访问到某个节点的情况。
如果 A 树对应节点为空，那么我们直接复用 B 树节点。
如果 B 树对应节点为空，直接返回 A 树对应节点。
综上所述：如果 A 树或 B 树的对应节点为空，那么就直接返回另一颗树上的节点，否则递归到叶子节点时，我们合并两棵树对应节点并返回，并在整个过程中更新维护的信息。
从刚刚的算法流程中不难看出，一次线段树合并的复杂度是 O(两颗线段树公共部分) O(两颗线段树公共部分)O(两颗线段树公共部分) 的。由于数的总量为 O(nlogn)O(n \log n)O(nlogn) 合并量级总会不超过 O(nlogn)O(n \log n)O(nlogn)。但是空间常数也是巨大的，此时可以写个可并堆（左偏树）。
下面给出模版题 P4556 基于线段树合并的做法。（本题只需要使用树上差分的技巧，最后树上每个节点合并儿子对应线段树即可）
有帮助，赞一个