Skip to content

Li Chao Tree

Introduction

Luogu 4097 [HEOI2013] Segment

Support two operations in the Cartesian plane (forced online):

  1. 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)\).
  2. 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:

  1. 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.
  2. 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.
  3. 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
constexpr double eps = 1e-9;

int cmp(double x, double y) {  // floating-point numbers are used, so there are precision errors
  if (x - y > eps) return 1;
  if (y - x > eps) return -1;
  return 0;
}

//...

void upd(int root, int cl, int cr, int u) {  // update a range fully covered by the segment
  int &v = s[root], mid = (cl + cr) >> 1;
  int bmid = cmp(calc(u, mid), calc(v, mid));
  if (bmid == 1 || (!bmid && u < v))  // in this problem, remember to compare segment indices
    swap(u, v);
  int bl = cmp(calc(u, cl), calc(v, cl)), br = cmp(calc(u, cr), calc(v, cr));
  if (bl == 1 || (!bl && u < v)) upd(root << 1, cl, mid, u);
  if (br == 1 || (!br && u < v)) upd(root << 1 | 1, mid + 1, cr, u);
  // at most one of the two if conditions above holds, which guarantees the time complexity of the Li Chao tree
}

Splitting a segment:

Implementation
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void update(int root, int cl, int cr, int l, int r,
            int u) {  // locate the ranges fully covered by the inserted segment
  if (l <= cl && cr <= r) {
    upd(root, cl, cr, u);  // the current range is fully covered: update its tag
    return;
  }
  int mid = (cl + cr) >> 1;
  if (l <= mid) update(root << 1, cl, mid, l, r, u);  // split the range recursively
  if (mid < r) update(root << 1 | 1, mid + 1, cr, l, r, u);
}

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
pdi query(int root, int l, int r, int d) {  // query
  if (r < d || d < l) return {0, 0};
  int mid = (l + r) >> 1;
  double res = calc(s[root], d);
  if (l == r) return {res, s[root]};
  return pmax({res, s[root]}, pmax(query(root << 1, l, mid, d),
                                   query(root << 1 | 1, mid + 1, r, d)));
}

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
#include <iostream>
constexpr int MOD1 = 39989;
constexpr int MOD2 = 1000000000;
constexpr int MAXT = 40000;
using namespace std;
using pdi = pair<double, int>;

constexpr double eps = 1e-9;

int cmp(double x, double y) {
  if (x - y > eps) return 1;
  if (y - x > eps) return -1;
  return 0;
}

struct line {
  double k, b;
} p[100005];

int s[160005];
int cnt;

double calc(int id, int d) { return p[id].b + p[id].k * d; }

void add(int x0, int y0, int x1, int y1) {
  cnt++;
  if (x0 == x1)  // special case: the line is vertical and has no slope
    p[cnt].k = 0, p[cnt].b = max(y0, y1);
  else
    p[cnt].k = 1.0 * (y1 - y0) / (x1 - x0), p[cnt].b = y0 - p[cnt].k * x0;
}

void upd(int root, int cl, int cr, int u) {  // update a range fully covered by the segment
  int &v = s[root], mid = (cl + cr) >> 1;
  int bmid = cmp(calc(u, mid), calc(v, mid));
  if (bmid == 1 || (!bmid && u < v)) swap(u, v);
  int bl = cmp(calc(u, cl), calc(v, cl)), br = cmp(calc(u, cr), calc(v, cr));
  if (bl == 1 || (!bl && u < v)) upd(root << 1, cl, mid, u);
  if (br == 1 || (!br && u < v)) upd(root << 1 | 1, mid + 1, cr, u);
}

void update(int root, int cl, int cr, int l, int r,
            int u) {  // locate the ranges fully covered by the inserted segment
  if (l <= cl && cr <= r) {
    upd(root, cl, cr, u);
    return;
  }
  int mid = (cl + cr) >> 1;
  if (l <= mid) update(root << 1, cl, mid, l, r, u);
  if (mid < r) update(root << 1 | 1, mid + 1, cr, l, r, u);
}

pdi pmax(pdi x, pdi y) {  // max function for pairs
  if (cmp(x.first, y.first) == -1)
    return y;
  else if (cmp(x.first, y.first) == 1)
    return x;
  else
    return x.second < y.second ? x : y;
}

pdi query(int root, int l, int r, int d) {  // query
  if (r < d || d < l) return {0, 0};
  int mid = (l + r) >> 1;
  double res = calc(s[root], d);
  if (l == r) return {res, s[root]};
  return pmax({res, s[root]}, pmax(query(root << 1, l, mid, d),
                                   query(root << 1 | 1, mid + 1, r, d)));
}

int main() {
  ios::sync_with_stdio(false);
  int n, lastans = 0;
  cin >> n;
  while (n--) {
    int op;
    cin >> op;
    if (op == 1) {
      int x0, y0, x1, y1;
      cin >> x0 >> y0 >> x1 >> y1;
      x0 = (x0 + lastans - 1 + MOD1) % MOD1 + 1,
      x1 = (x1 + lastans - 1 + MOD1) % MOD1 + 1;
      y0 = (y0 + lastans - 1 + MOD2) % MOD2 + 1,
      y1 = (y1 + lastans - 1 + MOD2) % MOD2 + 1;
      if (x0 > x1) swap(x0, x1), swap(y0, y1);
      add(x0, y0, x1, y1);
      update(1, 1, MOD1, x0, x1, cnt);
    } else {
      int x;
      cin >> x;
      x = (x + lastans - 1 + MOD1) % MOD1 + 1;
      cout << (lastans = query(1, 1, MOD1, x).second) << endl;
    }
  }
  return 0;
}

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.

  1. If \(v\) is empty, stop.

  2. If \(u\) is empty, copy \(v\) into \(u\).

  3. Insert the segment stored at \(v\) into the subtree rooted at \(u\).

  4. 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
void upd(int &root, int cl, int cr,
         int u) {  // several Li Chao trees are merged, so use dynamic node allocation.
  static int idx = 0;
  if (!root) {
    s[root = ++idx] = u;
    return;
  }
  int &v = s[root], mid = (cl + cr) >> 1;
  int bmid = cmp(calc(u, mid), calc(v, mid));
  if (bmid == 1 || (!bmid && u < v)) swap(u, v);
  int bl = cmp(calc(u, cl), calc(v, cl)), br = cmp(calc(u, cr), calc(v, cr));
  if (bl == 1 || (!bl && u < v)) upd(ls[root], cl, mid, u);
  if (br == 1 || (!br && u < v)) upd(rs[root], mid + 1, cr, u);
}

int merge(int &u, int &v, int l, int r) {
  if (!u || !v) {
    return u + v;
  }
  if (l == r) {
    int b = cmp(calc(s[v], l), calc(s[u], l));
    if (b == 1 || (!b && s[v] < s[u])) return v;
    return u;
  }
  upd(u, l, r, s[v]);
  int mid = (l + r) >> 1;
  ls[u] = merge(ls[u], ls[v], l, mid);
  rs[u] = merge(rs[u], rs[v], mid + 1, r);
  return u;
}

Practice problems

[JSOI2008] Blue Mary Starts a Company

[CodeChef] TSUM2 Sum on Tree

[USACO13MAR] Hill Walk G

[CF932F] Escape Through Leaf