Li Chao Tree
Maintain dynamic line insertion and min/max queries by storing line candidates in a segment tree over x-values.
Interactive visualization
Use the controls to connect the idea to concrete operations before diving into the full write-up.
interval [0, 3]
stored best line candidate: y = x + 1
interval [4, 7]
stored best line candidate: y = -x + 8
interval [0, 7]
stored best line candidate: y = 2x
Segment tree over x-domain
A Li Chao tree stores line candidates by x-interval. At each node, the line that wins at the midpoint stays, and the losing line is pushed to the side where it might still become optimal.
Family
Range queries
Static and dynamic range aggregates via indexed trees, segment trees, and precomputed tables.
Builds on
2 topics
Read these first if you want the surrounding context.
Unlocks
0 next topics
Use these follow-ups when you want to apply the current idea in a richer setting.
Learning paths
2
This topic appears in curated progressions so you can keep moving without guessing the next step.
Problem
Static Convex Hull Trick variants often need monotonic slopes, monotonic queries, or sortable intersection points.
What if lines arrive online in arbitrary order and you still want fast best-line queries at x?
Core idea
Build a segment tree over the x-domain.
Each node stores one candidate line. Compare the current node line and the inserted line at the midpoint:
- keep the better line at the midpoint in the node
- recurse with the worse line only into the side where it might still win
That local midpoint decision is enough to maintain the global envelope.
Why it matters
Li Chao is the dynamic, segment-tree flavored version of line-envelope optimization.
It trades some geometric elegance for much easier online updates.
Complexity
| Operation | Time |
|---|---|
| Insert one line | |
| Query best value at x |
Here X refers to the coordinate domain size or compressed coordinate count.
Key takeaways
- Li Chao tree solves dynamic line insertion plus min/max queries
- It is the natural next step after learning the idea behind Convex Hull Trick
- The data structure feels like a segment tree because it literally is one over the x-domain
- This is rare advanced material, but very high signal once DP optimizations become dynamic
Practice problems
| Problem | Difficulty | Key idea |
|---|---|---|
| Line Add Get Min | 🔴 Hard | Canonical Li Chao benchmark |
| Li Chao references | 🔴 Hard | Midpoint-based line swapping |
| Dynamic DP optimization references | 🔴 Hard | Online envelope maintenance |
Relation to other topics
- Convex Hull Trick provides the geometric optimization idea
- Segment Tree explains the interval recursion shape of the structure
- Persistent Segment Tree is another advanced segment-tree variant, but for versioning rather than line envelopes
Build on these first
These topics supply the mental model or underlying structure that this page assumes.
Segment Tree
Answer range queries and point updates in O(log n). Segment trees are the go-to structure for range sum, range min, and similar problems.
Convex Hull Trick
Maintain a set of lines so DP transitions of the form m*x + b can be optimized by querying only the best candidate line.
Related directions
These topics live nearby conceptually, even if they are not direct prerequisites.
More from Range queries
Stay in the same family when you want parallel variations of the same mental model.
Prefix Sum
Precompute cumulative totals so any range sum becomes one subtraction. Prefix sums are the first serious range-query idea everyone should know.
Difference Array
Apply many range updates in O(1) each, then rebuild the final values with one prefix pass. Difference arrays are the update-side twin of prefix sums.
Fenwick Tree (Binary Indexed Tree)
Maintain prefix sums with O(log n) updates and queries using one tiny bit trick. Fenwick trees are the lightest dynamic range-query structure worth knowing.
Mo's Algorithm
Reorder offline range queries so a moving window can answer them with small pointer adjustments instead of rebuilding from scratch.
Paths that include this topic
Follow one of these sequences if you want a guided next step instead of open-ended browsing.
Range-query toolkit
Start with static prefix tricks, then move into offline, persistent, dynamic, and precomputed range-query structures.
DP optimization
Turn transition formulas into line queries and move from hull geometry to dynamic Li Chao trees.
From the blog
Pair the atlas with recent writing from the rest of the site when you want a broader engineering perspective alongside the topic graph.