李超线段树不能维护区间凸壳，仅支持单点查询和区间插入单条线段；其“凸壳”是中点优势线段的近似结构，节点不保存完整凸壳信息，无法合并出真实分段线性凸壳。
李超线段树维护区间一次函数凸壳的核心限制
李超线段树本质上不支持「区间查询凸壳」或「区间插入多条线段后直接提取整个区间的上凸壳/下凸壳」。它只支持单点查询（query(x)）和区间插入（insert(l, r, k, b)），且插入的是单条线段（即一次函数 k * x + b）在区间 [l, r] 上的**有效部分**。所谓“维护凸壳”，其实是靠插入时的标记永久化策略，让每个线段树节点只存一条“优势线段”——在该节点对应区间中点处取值最大的那条（对上凸壳而言）。这不是真正的凸壳结构，而是能回答任意 x 处最大函数值的近似结构。
为什么不能直接用李超树做区间凸壳合并
因为李超树节点之间没有凸壳信息传递机制：两个子节点各自存了一条优势线段，但父节点不会、也不能自动合并出覆盖整个区间的上凸壳（可能需要 2 条甚至更多线段）。真实凸壳在长度为 n 的区间上最多有 O(n) 段，而李超树每个节点只存 1 条，信息严重压缩。常见错误是以为调用 query(l), query(l+1), ..., query(r) 就能得到凸壳折点——实际只是离散采样，无法还原分段线性结构。
想得到区间 [L, R] 上的实际上凸壳，得换思路
如果必须获取完整凸壳（即所有拐点及每段的 k, b），李超线段树不是合适工具。可行替代方案包括：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 离线处理：把所有一次函数按斜率排序，用单调栈维护凸壳（适用于静态、全局插入）
- 分治 + 合并凸壳：对区间操作建线段树，每个节点存完整的凸壳（用 vector 存断点），合并时用双指针归并两条凸壳（
O(len1 + len2)），空间和时间都是O(n log n)，比李超树重得多但结果精确 - 动态凸包数据结构（如李超树的变种 Li-Chao Tree with hull merging），但标准实现极少开源，且常要求函数可离散化、x 坐标固定
- 若只需查询某点最值，坚持用李超树：插入用
insert(l, r, k, b)，查询用query(x)，这是它唯一被证明高效的场景
插入一次函数时的常见坑
李超树插入线段 y = k*x + b 到区间 [l, r]，容易忽略以下细节：
立即学习“C++免费学习笔记（深入）”；
-
l和r必须是整数坐标，且线段树通常基于离散化后的坐标建树；若原问题 x 是实数，需提前离散化或改用动态开点 + 浮点中点判断（极不稳定） - 插入函数前，要确保当前节点区间
[tl, tr]与[l, r]有交集，否则跳过；标准写法是先if (r - 比较两条线段谁更优，不能只比中点
mid处函数值，还要递归下推：当新线段在mid更优，旧线段在tl或tr更优时，需将旧线段下推到对应子树（否则漏信息） - 若维护上凸壳，比较逻辑是：
new_f(mid) > old_f(mid)；若维护下凸壳，则反过来。混用会导致查询结果恒错 - 懒惰下推不是必须的，但“标记永久化”意味着每次插入都可能修改路径上多个节点的存储线段，不能简单覆盖
真正难的从来不是写对单次插入，而是在多次插入后仍保证任意 x 查询的正确性——这依赖于中点比较 + 两边递归的严格性，少一个分支就漏线段。
