引言
在计算几何和动态规划中，经常遇到这样的问题：维护一组直线，支持插入一条直线和查询某 x 坐标处的最小/最大值。朴素的暴力做法是查询时遍历所有直线，时间复杂度 O(n)。
李超线段树（Li Chao Segment Tree） 由李超在 2010 年提出，能够在 O(log C) 时间内完成直线插入和单点查询，其中 C 为 x 坐标值域。它比传统的凸包优化（Convex Hull Trick）更通用——不需要直线按斜率排序，支持任意顺序的插入操作。
本文将用 Java 完整实现李超线段树，并展示其在动态规划优化和计算几何问题中的应用。
算法原理
问题定义
维护一个直线集合 S，支持：
1. 插入直线：y = kx + b
2. 单点查询：给定 x，求 min/max{y_i(x) | y_i ∈ S}
核心思想
李超线段树是一棵以 x 坐标为下标的线段树。每个节点维护一条”在该节点代表区间的中点处最优”的直线。
对于区间 [l, r]，设中点 mid = (l + r) / 2：
– 节点中存储的直线 best，是在 mid 处取值最优（最小或最大）的直线
– 当插入新直线 newLine 时，比较两条直线在 l、mid、r 处的取值：
– 如果 newLine 在 mid 处更优，则替换 best，并将原来的 best 下放到更优的一侧子树
– 如果 newLine 只在左半或右半更优，则将其下放到对应子树继续比较
为什么只需要比较中点？
两条不同的直线最多相交一次。如果在 mid 处 newLine 优于 best，那么：
– 在 mid 的一侧，best 可能更优（因为直线相交）
– 在 mid 的另一侧，newLine 一定更优
因此，被替换下来的直线只需要在可能更优的一侧继续竞争。
Java 实现
1. 基础李超线段树
/**
* 直线类：y = k * x + b
*/
class Line {
long k; // 斜率
long b; // 截距
public Line(long k, long b) {
this.k = k;
this.b = b;
}
/**
* 计算直线在x处的值
*/
public long evaluate(long x) {
return k * x + b;
}
@Override
public String toString() {
return String.format("y = %dx + %d", k, b);
}
}
/**
* 李超线段树 - 维护动态直线集合，支持O(log C)的插入和查询
* 默认维护最小值（查询某x处的最小y值）
*/
public class LiChaoSegmentTree {
// x坐标范围
private final long xMin;
private final long xMax;
// 动态开点节点
private static class Node {
Line line; // 该节点维护的直线
Node left; // 左子树 [l, mid]
Node right; // 右子树 [mid+1, r]
Node(Line line) {
this.line = line;
}
}
private Node root;
private final boolean queryMax; // true=求最大值, false=求最小值
/**
* 构造函数
* @param xMin x坐标最小值
* @param xMax x坐标最大值
* @param queryMax true表示查询最大值，false表示查询最小值
*/
public LiChaoSegmentTree(long xMin, long xMax, boolean queryMax) {
this.xMin = xMin;
this.xMax = xMax;
this.queryMax = queryMax;
// 初始化为水平线：最小值时+y无穷，最大值时-y无穷
if (queryMax) {
this.root = new Node(new Line(0, Long.MIN_VALUE));
} else {
this.root = new Node(new Line(0, Long.MAX_VALUE));
}
}
/**
* 便捷构造函数：默认查询最小值
*/
public LiChaoSegmentTree(long xMin, long xMax) {
this(xMin, xMax, false);
}
/**
* 插入一条直线
*/
public void insertLine(long k, long b) {
insertLine(root, xMin, xMax, new Line(k, b));
}
private void insertLine(Node node, long l, long r, Line newLine) {
long mid = l + (r - l) / 2;
boolean left = isBetter(newLine.evaluate(l), node.line.evaluate(l));
boolean m = isBetter(newLine.evaluate(mid), node.line.evaluate(mid));
boolean right = isBetter(newLine.evaluate(r), node.line.evaluate(r));
// 如果新直线在中点更优，交换两条直线
if (m) {
Line temp = node.line;
node.line = newLine;
newLine = temp;
}
// 如果l==r，无需继续
if (l == r) return;
// 判断新直线在哪一侧可能更优
// 注意：交换后，node.line是在mid处最优的，newLine是待下放的
boolean leftNewBetter = isBetter(newLine.evaluate(l), node.line.evaluate(l));
boolean rightNewBetter = isBetter(newLine.evaluate(r), node.line.evaluate(r));
if (leftNewBetter) {
if (node.left == null) {
node.left = new Node(newLine);
} else {
insertLine(node.left, l, mid, newLine);
}
} else if (rightNewBetter) {
if (node.right == null) {
node.right = new Node(newLine);
} else {
insertLine(node.right, mid + 1, r, newLine);
}
}
// 如果两侧都不更优，新直线完全被覆盖，无需插入
}
/**
* 判断val1是否比val2更优
*/
private boolean isBetter(long val1, long val2) {
return queryMax ? val1 > val2 : val1 < val2;
}
/**
* 查询x坐标处的最优值
*/
public long query(long x) {
return query(root, xMin, xMax, x);
}
private long query(Node node, long l, long r, long x) {
if (node == null) {
return queryMax ? Long.MIN_VALUE : Long.MAX_VALUE;
}
long res = node.line.evaluate(x);
if (l == r) return res;
long mid = l + (r - l) / 2;
if (x <= mid) {
long leftRes = query(node.left, l, mid, x);
return queryMax ? Math.max(res, leftRes) : Math.min(res, leftRes);
} else {
long rightRes = query(node.right, mid + 1, r, x);
return queryMax ? Math.max(res, rightRes) : Math.min(res, rightRes);
}
}
}
2. 李超树节点池优化版
/**
* 使用节点池优化的李超线段树
* 避免频繁创建对象，适合高性能场景
*/
public class LiChaoSegmentTreeOptimized {
private static final int MAX_NODES = 4000000; // 预分配节点数
private static class Line {
long k, b;
boolean isValid;
Line() { this.isValid = false; }
Line(long k, long b) { this.k = k; this.b = b; this.isValid = true; }
long evaluate(long x) {
return k * x + b;
}
}
// 节点池
private final Line[] lines;
private final int[] leftChild;
private final int[] rightChild;
private int nodeCount;
private final long xMin, xMax;
private final boolean queryMax;
private final long INF = Long.MAX_VALUE / 4;
private int root;
public LiChaoSegmentTreeOptimized(long xMin, long xMax, boolean queryMax) {
this.xMin = xMin;
this.xMax = xMax;
this.queryMax = queryMax;
this.lines = new Line[MAX_NODES];
this.leftChild = new int[MAX_NODES];
this.rightChild = new int[MAX_NODES];
// 初始化根节点
this.root = newNode();
if (queryMax) {
lines[root] = new Line(0, -INF);
} else {
lines[root] = new Line(0, INF);
}
}
private int newNode() {
lines[nodeCount] = new Line();
leftChild[nodeCount] = -1;
rightChild[nodeCount] = -1;
return nodeCount++;
}
public void insertLine(long k, long b) {
insert(root, xMin, xMax, new Line(k, b));
}
private void insert(int node, long l, long r, Line newLine) {
long mid = l + (r - l) / 2;
Line curLine = lines[node];
if (!curLine.isValid) {
lines[node] = newLine;
return;
}
// 确保node.line在mid处更优
boolean newBetterAtMid = isBetter(newLine.evaluate(mid), curLine.evaluate(mid));
if (newBetterAtMid) {
Line temp = lines[node];
lines[node] = newLine;
newLine = temp;
curLine = lines[node];
}
if (l == r) return;
// 判断在哪一侧新直线可能更优
boolean leftBetter = isBetter(newLine.evaluate(l), curLine.evaluate(l));
boolean rightBetter = isBetter(newLine.evaluate(r), curLine.evaluate(r));
if (leftBetter) {
if (leftChild[node] == -1) {
leftChild[node] = newNode();
lines[leftChild[node]] = newLine;
} else {
insert(leftChild[node], l, mid, newLine);
}
} else if (rightBetter) {
if (rightChild[node] == -1) {
rightChild[node] = newNode();
lines[rightChild[node]] = newLine;
} else {
insert(rightChild[node], mid + 1, r, newLine);
}
}
}
private boolean isBetter(long v1, long v2) {
return queryMax ? v1 > v2 : v1 < v2;
}
public long query(long x) {
return query(root, xMin, xMax, x);
}
private long query(int node, long l, long r, long x) {
if (node == -1 || !lines[node].isValid) {
return queryMax ? -INF : INF;
}
long res = lines[node].evaluate(x);
if (l == r) return res;
long mid = l + (r - l) / 2;
if (x <= mid && leftChild[node] != -1) {
long leftRes = query(leftChild[node], l, mid, x);
return queryMax ? Math.max(res, leftRes) : Math.min(res, leftRes);
} else if (x > mid && rightChild[node] != -1) {
long rightRes = query(rightChild[node], mid + 1, r, x);
return queryMax ? Math.max(res, rightRes) : Math.min(res, rightRes);
}
return res;
}
}
3. 完整测试与演示
/**
* 李超线段树测试与演示
*/
public class LiChaoDemo {
public static void main(String[] args) {
// 测试1：基础功能
System.out.println("=== 基础功能测试 ===");
LiChaoSegmentTree lichao = new LiChaoSegmentTree(-10, 10, false);
// 插入几条直线
lichao.insertLine(1, 0); // y = x
lichao.insertLine(-1, 5); // y = -x + 5
lichao.insertLine(0, 3); // y = 3
lichao.insertLine(2, -5); // y = 2x - 5
// 查询各点的最小值
for (int x = -5; x <= 5; x++) {
long minVal = lichao.query(x);
System.out.printf("x=%d, min=%d%n", x, minVal);
}
// 测试2：最大值版本
System.out.println("\n=== 最大值版本测试 ===");
LiChaoSegmentTree lichaoMax = new LiChaoSegmentTree(-10, 10, true);
lichaoMax.insertLine(1, 0);
lichaoMax.insertLine(-1, 5);
lichaoMax.insertLine(0, 3);
for (int x = -5; x <= 5; x++) {
long maxVal = lichaoMax.query(x);
System.out.printf("x=%d, max=%d%n", x, maxVal);
}
// 测试3：验证正确性
System.out.println("\n=== 正确性验证 ===");
LiChaoSegmentTree verify = new LiChaoSegmentTree(-100, 100, false);
java.util.List<Line> lines = new java.util.ArrayList<>();
java.util.Random rand = new java.util.Random(42);
for (int i = 0; i < 100; i++) {
long k = rand.nextInt(200) - 100;
long b = rand.nextInt(200) - 100;
verify.insertLine(k, b);
lines.add(new Line(k, b));
}
// 随机查询10个点，与李超树结果对比
for (int i = 0; i < 10; i++) {
long x = rand.nextInt(201) - 100;
long treeResult = verify.query(x);
// 暴力计算
long bruteResult = Long.MAX_VALUE;
for (Line line : lines) {
bruteResult = Math.min(bruteResult, line.evaluate(x));
}
boolean match = treeResult == bruteResult;
System.out.printf("x=%d, tree=%d, brute=%d, match=%s%n",
x, treeResult, bruteResult, match);
}
// 测试4：性能测试
System.out.println("\n=== 性能测试 ===");
LiChaoSegmentTree perf = new LiChaoSegmentTree(-1000000, 1000000, false);
long start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
perf.insertLine(rand.nextInt(1000), rand.nextInt(1000));
}
long insertTime = System.currentTimeMillis() - start;
start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
perf.query(rand.nextInt(2000001) - 1000000);
}
long queryTime = System.currentTimeMillis() - start;
System.out.println("10万次插入耗时: " + insertTime + "ms");
System.out.println("10万次查询耗时: " + queryTime + "ms");
}
}
4. 实战应用：DP优化
/**
* 李超线段树在动态规划中的应用
* 问题：将序列分成若干段，每段代价为 (sum_i - sum_j)^2 + C
* 求最小总代价
*
* DP方程：dp[i] = min{dp[j] + (sum[i] - sum[j])^2 + C} for j < i
* 展开：dp[i] = min{dp[j] + sum[j]^2 - 2*sum[i]*sum[j]} + sum[i]^2 + C
*
* 对于固定的j，令 k = -2*sum[j], b = dp[j] + sum[j]^2
* 则 dp[i] = min{k * sum[i] + b} + sum[i]^2 + C
*
* 这就是李超线段树的经典应用场景！
*/
public class DPOptimization {
/**
* 使用李超线段树优化的DP
* @param arr 原数组
* @param C 分段额外代价
* @return 最小总代价
*/
public long solve(long[] arr, long C) {
int n = arr.length;
// 前缀和
long[] sum = new long[n + 1];
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + arr[i - 1];
}
// dp[i] 表示前i个元素的最小代价
long[] dp = new long[n + 1];
dp[0] = 0;
// 李超线段树维护最小值
// x的范围是sum的可能取值范围
long xMin = 0, xMax = 0;
for (long s : sum) {
xMin = Math.min(xMin, s);
xMax = Math.max(xMax, s);
}
LiChaoSegmentTree lichao = new LiChaoSegmentTree(xMin, xMax, false);
// 初始直线：j=0, k = -2*sum[0] = 0, b = dp[0] + sum[0]^2 = 0
lichao.insertLine(0, 0);
for (int i = 1; i <= n; i++) {
// 查询当前sum[i]处的最小值
long best = lichao.query(sum[i]);
dp[i] = best + sum[i] * sum[i] + C;
// 插入新的直线，供后续状态使用
long k = -2 * sum[i];
long b = dp[i] + sum[i] * sum[i];
lichao.insertLine(k, b);
}
return dp[n];
}
public static void main(String[] args) {
DPOptimization solver = new DPOptimization();
// 测试用例
long[] arr1 = {1, 2, 3, 4, 5};
long C1 = 10;
System.out.println("数组 [1,2,3,4,5], C=10, 最小代价: " + solver.solve(arr1, C1));
long[] arr2 = {5, 4, 3, 2, 1};
long C2 = 5;
System.out.println("数组 [5,4,3,2,1], C=5, 最小代价: " + solver.solve(arr2, C2));
// 大规模测试
java.util.Random rand = new java.util.Random(42);
long[] largeArr = new long[100000];
for (int i = 0; i < 100000; i++) {
largeArr[i] = rand.nextInt(100) + 1;
}
long start = System.currentTimeMillis();
long result = solver.solve(largeArr, 1000);
long time = System.currentTimeMillis() - start;
System.out.println("\n10万规模数组, 最小代价: " + result);
System.out.println("耗时: " + time + "ms");
}
}
复杂度分析
时间复杂度
- 插入直线：O(log C)，其中 C 为 x 值域范围。每次插入最多访问 O(log C) 个节点，每个节点进行常数次计算
- 单点查询：O(log C)，从根到叶子遍历
- 批量插入 n 条直线后查询 m 次：O((n + m) log C)
空间复杂度
- 动态开点：最坏情况 O(n log C)，n 为插入直线数。每条直线最多被存储在 O(log C) 个节点中
- 节点池优化版：预先分配固定空间，避免 GC 开销
与凸包优化的比较
| 特性 | 李超线段树 | 凸包优化（CHT） |
|---|---|---|
| 插入顺序 | 任意 | 需按斜率排序 |
| 查询顺序 | 任意 | 需按x排序 |
| 在线/离线 | 完全在线 | 通常离线 |
| 时间复杂度 | O(log C) | O(log n) 或 O(1) |
| 适用范围 | 任意x值域 | 连续x值域 |
| 实现复杂度 | 中等 | 较复杂 |
进阶扩展
1. 持久化李超树
与主席树类似，李超线段树也可以持久化。每次插入创建新版本的根节点，共享未修改的子树：
public PersistentLiChaoNode insertPersistent(PersistentLiChaoNode node, long l, long r, Line newLine) {
PersistentLiChaoNode newNode = clone(node);
// ... 标准插入逻辑，但创建新节点而非修改
return newNode;
}
2. 李超树的线段扩展
标准李超树维护的是直线（一次函数）。可以扩展到维护线段（只在某个 x 区间内有效）：
public void insertSegment(long k, long b, long xL, long xR) {
insertSegment(root, xMin, xMax, new Line(k, b), xL, xR);
}
private void insertSegment(Node node, long l, long r, Line newLine, long xL, long xR) {
if (xR < l || r < xL) return; // 无交集
if (xL <= l && r <= xR) {
insertLine(node, l, r, newLine); // 完全覆盖，按直线处理
return;
}
// 部分覆盖，下推到子树
long mid = l + (r - l) / 2;
if (node.left == null) node.left = new Node(queryMax ? ...);
if (node.right == null) node.right = new Node(queryMax ? ...);
insertSegment(node.left, l, mid, newLine, xL, xR);
insertSegment(node.right, mid + 1, r, newLine, xL, xR);
}
3. 二维李超树
扩展到二维平面，维护平面上的直线（形如 z = ax + by + c），支持在 (x, y) 处查询最值。实现方式是将外层李超树的每个节点再维护一棵内层李超树，复杂度为 O(log² C)。
应用场景
1. 动态规划优化（斜率优化DP）
如本文 DP 示例所示，当 DP 转移方程可以化为 dp[i] = min{k_j * x_i + b_j} 的形式时，李超线段树可以替代凸包优化，且不需要对查询排序。
2. 计算几何
维护一组直线，实时查询某垂直线 x = x₀ 与所有直线的交点中的最高/最低点。
3. 资源调度
每个任务有一条”效率-时间”直线，查询在给定时间限制下能达到的最大效率。
4. 在线凸包
在需要支持动态插入且查询顺序不确定的场景下，李超树是凸包问题的有效替代方案。
总结
李超线段树通过中点比较和单侧下放的巧妙设计，实现了任意顺序直线插入的 O(log C) 维护。本文的 Java 实现展示了：
- 动态开点：按需创建节点，节省内存
- 节点池优化：预分配避免 GC，提升性能
- 最值切换：通过
queryMax参数支持最小值和最大值两种模式 - DP优化实战：将斜率优化DP的 O(n²) 降到 O(n log C)
在算法竞赛和工程实践中，李超线段树是处理动态直线最值问题的利器，尤其在查询顺序不确定的在线场景中，它是凸包优化的完美替代方案。
