Li Chao Tree
Introduction
Luogu 4097 [HEOI2013] Segment
Support two operations in the Cartesian plane (forced online):
- Add a segment to the plane. The \(i\)-th segment inserted has index \(i\), and its two endpoints are \((x_0,y_0)\) and \((x_1,y_1)\).
- Given a number \(k\), among the segments that intersect the line \(x = k\), find the index of the one whose intersection point has the largest y-coordinate (if several segments attain this largest y-coordinate, output the smallest index among them). If no segment intersects the given line, output \(0\).
Constraints: the total number of operations satisfies \(1 \leq n \leq 10^5\), and \(1 \leq k, x_0, x_1 \leq 39989\), \(1 \leq y_0, y_1 \leq 10^9\).
An ordinary segment tree cannot maintain this kind of information well. The Li Chao tree was devised for exactly this situation.
Procedure
We can restate the task as supporting the following operations:
- Add a linear function with domain \([l,r]\).
- Given \(k\), among all linear functions whose domain contains \(k\), find the one with the largest value at \(x=k\). If several functions have the same value, choose the one with the smallest index.
Note
A segment perpendicular to the \(x\)-axis leads to a division by zero. If its endpoints are \((x,y_0)\) and \((x,y_1)\) with \(y_0<y_1\), insert the linear function \(f(x)=0\cdot x+y_1\) with domain \([x,x]\).
This is a range update, so we do what segment trees usually do for range problems and give every node a lazy tag. The lazy tag of a node \(i\) is a segment, denoted \(l_i\). It means that the whole range of the node is to be updated with \(l_i\).
Suppose we are inserting a segment \(f\), and consider a segment tree range that the new segment \(f\) covers completely. If the range has no tag, we simply tag it with this segment.
If the range already has a tag, we have to push a tag down, because tags are hard to merge. But the children have tags of their own, which may conflict in turn, so we push tags down recursively.
As the figure shows, the current range splits into two subranges according to whether the new segment \(f\) lies above the old tag \(g\). One of these subranges is always contained entirely in the left half or in the right half. In other words, one of the two segments can be the answer only in the left half, or only in the right half. We recursively update the corresponding subtree with that segment and use the other one as the lazy tag of the whole range. This is what bounds the cost of the recursive push-down. A segment is pushed down only when it can be the answer in just one of the two halves, so there is no danger of losing a segment.
In detail, let \(m\) be the midpoint of the current range. We compare the value of the new segment \(f\) at the midpoint with the value of the previously best segment \(g\) there.
If the new segment \(f\) is better, swap \(f\) and \(g\). So now consider the case where \(f\) is worse than \(g\) at the midpoint:
- If \(f\) is better at the left endpoint, then \(f\) and \(g\) must intersect in the left half, and \(f\) can be better than \(g\) only in the left half. Recurse into the left child to push it down.
- If \(f\) is better at the right endpoint, then \(f\) and \(g\) must intersect in the right half, and \(f\) can be better than \(g\) only in the right half. Recurse into the right child to push it down.
- If \(g\) is better at both endpoints, \(f\) can never be the answer, and there is nothing more to push down.
There is one more case besides these three: \(f\) and \(g\) intersect exactly at the midpoint. An implementation can treat it as part of the case where \(f\) is worse than \(g\) at the midpoint; the recursion then pushes \(f\) down toward the endpoint at which it is better.
Finally, \(g\) becomes the lazy tag of the current range.
Pushing a tag down:
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | |
Splitting a segment:
Implementation
1 2 3 4 5 6 7 8 9 10 | |
Note that the lazy tag of a range is not the same thing as the segment with the largest value at the midpoint of that range.
In the figure, after the yellow segment is added, only the tags of the red nodes are updated; the tags of the green nodes are unchanged. Yet the yellow segment clearly has the largest value at the midpoints of the second, third and fourth green ranges.
To answer a query we use the idea of permanent tags: among the tag segments of all segment tree ranges that contain \(x\) (there are at most \(O(\log n)\) of them), we compare and take the best.
Query:
Implementation
1 2 3 4 5 6 7 8 | |
From the description above, a query clearly takes \(O(\log n)\) time. An insertion splits the segment into \(O(\log n)\) ranges and spends another \(O(\log n)\) on the recursive push-down in each of them, so it takes \(O(\log^2 n)\) time.
[HEOI2013] Segment reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | |
Merging
Much like merging ordinary segment trees, we define the following procedure, which merges two Li Chao tree nodes \(u\) and \(v\) and makes \(u\) the new root.
-
If \(v\) is empty, stop.
-
If \(u\) is empty, copy \(v\) into \(u\).
-
Insert the segment stored at \(v\) into the subtree rooted at \(u\).
-
Recursively merge the left subtrees of \(u\) and \(v\), and likewise their right subtrees.
If merging several Li Chao trees involves \(n\) nodes in total, the procedure takes \(O(n\log n)\) time. Take the node that holds any given segment: every time the segment is moved, either its depth changes by \(+1\) or it is deleted from the tree outright. Both operations cost \(O(1)\), and the depth of a node is at most \(O(\log n)\), which gives the bound.
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | |
Practice problems
[JSOI2008] Blue Mary Starts a Company
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: StudyingFather, 24OI-bot, leoleoasd, Enter-tainer, kenlig, ksyx, Ir1d, mcendu, do-while-true, codewasp942, zirnc, henrytbtrue, iamtwz, Persdre, shuzhouliu, CoelacanthusHex, aofall, Marcythm, Tiphereth-A, Jelefy, usada-pekora-286, HeRaNO, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.