李超线段树
引入
[洛谷 4097 [HEOI2013]Segment](https://www.luogu.com.cn/problem/P4097)
要求在平面直角坐标系下维护两个操作（强制在线）：
- 在平面上加入一条线段．记第 𝑖i
条被插入的线段的标号为 𝑖i，该线段的两个端点分别为 (𝑥0,𝑦0)(x0,y0)，(𝑥1,𝑦1)(x1,y1)． - 给定一个数 𝑘k，询问与直线 𝑥 =𝑘x=k 相交的线段中，交点纵坐标最大的线段的编号（若有多条线段与查询直线的交点纵坐标都是最大的，则输出编号最小的线段）．特别地，若不存在线段与给定直线相交，输出 00．
数据满足：操作总数 1 ≤𝑛 ≤1051≤n≤105，1 ≤𝑘,𝑥0,𝑥1 ≤399891≤k,x0,x1≤39989，1 ≤𝑦0,𝑦1 ≤1091≤y0,y1≤109．
我们发现，传统的线段树无法很好地维护这样的信息．这种情况下，李超线段树 便应运而生．
过程
我们可以把任务转化为维护如下操作：
- 加入一个一次函数，定义域为 [𝑙,𝑟][l,r]；
- 给定 𝑘k，求定义域包含 𝑘k 的所有一次函数中，在 𝑥 =𝑘x=k 处取值最大的那个，如果有多个函数取值相同，选编号最小的．
注意
当线段垂直于 𝑥x 轴时，会出现除以零的情况．假设线段两端点分别为 (𝑥,𝑦0)(x,y0) 和 (𝑥,𝑦1)(x,y1)，𝑦0 <𝑦1y0<y1，则插入定义域为 [𝑥,𝑥][x,x] 的一次函数 𝑓(𝑥) =0 ⋅𝑥 +𝑦1f(x)=0⋅x+y1．
看到区间修改，我们按照线段树解决区间问题的常见方法，给每个节点一个懒标记．每个节点 𝑖i 的懒标记都是一条线段，记为 𝑙𝑖li，表示要用 𝑙𝑖li 更新该节点所表示的整个区间．
现在我们需要插入一条线段 𝑓f，考虑某个被新线段 𝑓f 完整覆盖的线段树区间．若该区间无标记，直接打上用该线段更新的标记．
如果该区间已经有标记了，由于标记难以合并，只能把标记下传．但是子节点也有自己的标记，也可能产生冲突，所以我们要递归下传标记．
如图，按新线段 𝑓f 取值是否大于原标记 𝑔g，我们可以把当前区间分为两个子区间．其中 肯定有一个子区间被左区间或右区间完全包含 ，也就是说，在两条线段中，肯定有一条线段，只可能成为左区间的答案，或者只可能成为右区间的答案．我们用这条线段递归更新对应子树，用另一条线段作为懒标记更新整个区间，这就保证了递归下传的复杂度．当一条线段只可能成为左或右区间的答案时，才会被下传，所以不用担心漏掉某些线段．
具体来说，设当前区间的中点为 𝑚m，我们拿新线段 𝑓f 在中点处的值与原最优线段 𝑔g 在中点处的值作比较．
如果新线段 𝑓f 更优，则将 𝑓f 和 𝑔g 交换．那么现在考虑在中点处 𝑓f 不如 𝑔g 优的情况：
- 若在左端点处 𝑓f 更优，那么 𝑓f 和 𝑔g 必然在左半区间中产生了交点，𝑓f 只有在左区间才可能优于 𝑔g，递归到左儿子中进行下传；
- 若在右端点处 𝑓f 更优，那么 𝑓f 和 𝑔g 必然在右半区间中产生了交点，𝑓f 只有在右区间才可能优于 𝑔g，递归到右儿子中进行下传；
- 若在左右端点处 𝑔g 都更优，那么 𝑓f 不可能成为答案，不需要继续下传．
除了这两种情况之外，还有一种情况是 𝑓f 和 𝑔g 刚好交于中点，在程序实现时可以归入中点处 𝑓f 不如 𝑔g 优的情况，结果会往 𝑓f 更优的一个端点进行递归下传．
最后将 𝑔g 作为当前区间的懒标记．
下传标记：
实现
---|---
拆分线段：
实现
---|---
注意懒标记并不等价于在区间中点处取值最大的线段．
如图，加入黄色线段后，只有红色节点的标记被更新，而绿色节点的标记还未被改变．但在第二、三、四个绿色区间的中点处显然黄色线段取值最大．
查询时，我们可以利用标记永久化思想，在包含 𝑥x 的所有线段树区间（不超过 𝑂(log𝑛)O(logn) 个）的标记线段中，比较得出最终答案．
查询：
实现
---|---
根据上面的描述，查询过程的时间复杂度显然为 𝑂(log𝑛)O(logn)，而插入过程中，我们需要将原线段拆分到 𝑂(log𝑛)O(logn) 个区间中，对于每个区间，我们又需要花费 𝑂(log𝑛)O(logn) 的时间递归下传，从而插入过程的时间复杂度为 𝑂(log2𝑛)O(log2n)．
[[HEOI2013]Segment](https://www.luogu.com.cn/problem/P4097) 参考代码
---|---
合并
类似于普通线段树的合并，我们定义以下过程来将两个李超线段树节点 𝑢,𝑣u,v 合并，并以 𝑢u 作为新的根．
- 如果 𝑣v 为空，结束过程．
- 如果 𝑢u 为空，将 𝑣v 复制给 𝑢u．
- 将 𝑣v 对应线段插入到 𝑢u 为根的子树．
- 递归将 𝑢,𝑣u,v 的左右子树对应合并．
若合并若干李超线段树涉及的总点数为 𝑛n，则该过程的复杂度为 𝑂(𝑛log𝑛)O(nlogn)：对于任意线段在树上对应的节点，每次涉及移动它时，我们要么使其深度 +1+1，要么直接从树上删除，这两个操作的代价都是 𝑂(1)O(1) 的，而每个点深度至多为 𝑂(log𝑛)O(logn)，于是复杂度如上．
实现
---|---
## 习题
[「JSOI2008」Blue Mary 开公司](https://www.luogu.com.cn/problem/P4254)
[「CodeChef」TSUM2 Sum on Tree](https://www.codechef.com/problems/TSUM2)
[「USACO13MAR」Hill Walk G](https://www.luogu.com.cn/problem/P3081)
[「CF932F」Escape Through Leaf](https://codeforces.com/problemset/problem/932/F)
* * *
> __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/ds/li-chao-tree.md)
> __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/ds/li-chao-tree.md "edit.link.title")
> __本页面贡献者：[StudyingFather](https://github.com/StudyingFather), [Tiphereth-A](https://github.com/Tiphereth-A), [do-while-true](https://github.com/do-while-true), [iamtwz](https://github.com/iamtwz), [aofall](https://github.com/aofall), [c-forrest](https://github.com/c-forrest), [ChungZH](https://github.com/ChungZH), [codewasp942](https://github.com/codewasp942), [CoelacanthusHex](https://github.com/CoelacanthusHex), [Enter-tainer](https://github.com/Enter-tainer), [henrytbtrue](https://github.com/henrytbtrue), [HeRaNO](https://github.com/HeRaNO), [Ir1d](https://github.com/Ir1d), [Jelefy](https://github.com/Jelefy), [kenlig](https://github.com/kenlig), [ksyx](https://github.com/ksyx), [leoleoasd](https://github.com/leoleoasd), [Marcythm](https://github.com/Marcythm), [mcendu](https://github.com/mcendu), [Persdre](https://github.com/Persdre), [shuzhouliu](https://github.com/shuzhouliu), [usada-pekora-286](https://github.com/usada-pekora-286)
> __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用