Li Chao Tree

释义 Definition

李超树（Li Chao tree）是一种用于维护一组直线（通常形如 \(y=ax+b\)），并支持在给定 \(x\) 处快速查询最小值或最大值的树形数据结构。常用于优化动态规划、处理“直线最小/最大值查询”等问题（与“凸包优化”相关）。也存在支持动态插入、离散/连续坐标范围等变体。

发音 Pronunciation (IPA)

/liː ˈtʃaʊ triː/

例句 Examples

I used a Li Chao tree to query the minimum value at each x.
我用李超树来查询每个 x 位置上的最小值。

In the DP optimization, we insert lines as states change and use a Li Chao tree to answer min-cost queries efficiently.
在动态规划优化中，我们随着状态变化插入直线，并用李超树高效回答最小代价查询。

词源 Etymology

“Li Chao tree”得名于相关算法的提出者（李超，Li Chao）。该结构的核心思想是：在一棵按 \(x\) 区间划分的树上，每个节点保存一条“当前更优的直线”，并在比较两条直线在区间中点与端点的大小后，把可能更优的那条递归下放到左/右子区间，从而实现对“直线集合”的高效维护与查询。

相关词 Related Words

• Segment Tree
• Convex Hull Trick
• Dynamic Programming
• Fenwick Tree
• Binary Search Tree
• Divide And Conquer
• AtCoder Library

文学与作品 Literary Works

• Competitive Programming 3（Steven Halim 等）：在高级数据结构/优化技巧相关章节与题解讨论中常提到。
• AtCoder Library (ACL) Documentation：作为竞赛常用库与相关讨论中出现（含 Li Chao tree / Li Chao segment tree 的实现与用法）。
• *cp-algorithms (e-maxx)*：算法文章与教程中常以“Li Chao Tree”介绍其原理、复杂度与实现细节。