Skip to content

Li Chao Segment Tree

Introduction

Luogu 4097 [HEOI2013]Segment

Two operations need to be maintained in the Cartesian coordinate plane (forced online):

  1. Add a line segment to the plane. Let the label of the \(i\)-th inserted segment be \(i\), with endpoints \((x_0,y_0)\) and \((x_1,y_1)\).
  2. Given a number \(k\), query the label of the segment with the largest \(y\)-coordinate at the intersection with the line \(x = k\) (if multiple segments have the same maximum \(y\)-coordinate, output the smallest label). If no segment intersects the given line, output \(0\).

Data constraints: total operations \(1 \leq n \leq 10^5\), \(1 \leq k, x_0, x_1 \leq 39989\), \(1 \leq y_0, y_1 \leq 10^9\).

We find that traditional segment trees cannot efficiently maintain such information. In this case, the Li Chao Segment Tree comes into play.

Process

We can transform the task into maintaining 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 multiple functions have the same value, choose the one with the smallest label.
Note

When a segment is perpendicular to the \(x\)-axis, division by zero occurs. Assume the segment endpoints are \((x,y_0)\) and \((x,y_1)\) with \(y_0<y_1\). Then insert the linear function \(f(x)=0\cdot x+y_1\) with domain \([x,x]\).

Seeing interval modifications, we follow the common approach of segment trees for interval problems by assigning a lazy tag to each node. The lazy tag for each node \(i\) is a line segment, denoted as \(l_i\), indicating that \(l_i\) should be used to update the entire interval represented by this node.

Now we need to insert a line segment \(f\). Consider a segment tree interval that is completely covered by the new segment \(f\). If the interval has no tag, directly mark it with this segment.

If the interval already has a tag, since tags are difficult to merge, we can only push down the tag. However, child nodes also have their own tags, which may cause conflicts, so we need to recursively push down the tag.

As shown in the figure, based on whether the new segment \(f\) has a greater value than the original tag \(g\), we can divide the current interval into two subintervals. Among them, there must be one subinterval completely contained by either the left or right interval. That is, between the two line segments, there must be one segment that can only become the answer for the left interval or only become the answer for the right interval. We use this segment to recursively update the corresponding subtree and use the other segment as the lazy tag to update the entire interval. This ensures the complexity of recursive pushdown. A segment is only pushed down when it can only become the answer for the left or right interval, so there is no need to worry about missing some segments.

Specifically, let the midpoint of the current interval be \(m\). We compare the value of the new segment \(f\) at the midpoint with the value of the original optimal segment \(g\) at the midpoint.

If the new segment \(f\) is better, swap \(f\) and \(g\). 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 interval. \(f\) can only be better than \(g\) in the left interval, so recursively push down to the left child.
  2. If \(f\) is better at the right endpoint, then \(f\) and \(g\) must intersect in the right half interval. \(f\) can only be better than \(g\) in the right interval, so recursively push down to the right child.
  3. If \(g\) is better at both endpoints, then \(f\) cannot become the answer, and no further pushdown is needed.

Besides these two cases, there is another case where \(f\) and \(g\) intersect exactly at the midpoint. In implementation, this can be treated as the case where \(f\) is worse than \(g\) at the midpoint, and the result will recursively push down to the endpoint where \(f\) is better.

Finally, set \(g\) as the lazy tag for the current interval.

Push down tag:

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) {  // Due to floating-point numbers, there will be 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) {  // Modify intervals completely 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))  // Remember to compare segment labels in this problem
    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 above two if conditions holds, ensuring the time complexity of Li Chao Tree
}

Split 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 intervals completely covered by the inserted segment
  if (l <= cl && cr <= r) {
    upd(root, cl, cr, u);  // Completely cover the current interval, update the tag
    return;
  }
  int mid = (cl + cr) >> 1;
  if (l <= mid) update(root << 1, cl, mid, l, r, u);  // Recursively split intervals
  if (mid < r) update(root << 1 | 1, mid + 1, cr, l, r, u);
}

Note that the lazy tag is not equivalent to the segment with the largest value at the midpoint of the interval.

As shown in the figure, after adding the yellow segment, only the tags of the red nodes are updated, while the tags of the green nodes remain unchanged. However, at the midpoints of the second, third, and fourth green intervals, the yellow segment clearly has the largest value.

When querying, we can use the idea of permanent tags. Among the tag segments of all segment tree intervals containing \(x\) (no more than \(O(\log n)\)), we compare to obtain the final answer.

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)));
}

According to the above description, the time complexity of the query process is clearly \(O(\log n)\). During insertion, we need to split the original segment into \(O(\log n)\) intervals. For each interval, we spend \(O(\log n)\) time recursively pushing down. Thus, the time complexity of the insertion process is \(O(\log^2 n)\).

[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: line slope is undefined (vertical line)
    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) {  // Modify intervals 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 intervals 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) {  // Pair max function
  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

Similar to merging ordinary segment trees, we define the following process to merge two Li Chao Segment Tree nodes \(u\) and \(v\), using \(u\) as the new root.

  1. If \(v\) is empty, end the process.
  2. If \(u\) is empty, copy \(v\) to \(u\).
  3. Insert the segment corresponding to \(v\) into the subtree rooted at \(u\).
  4. Recursively merge the left and right subtrees of \(u\) and \(v\) correspondingly.

If the total number of nodes involved in merging several Li Chao Segment Trees is \(n\), the complexity of this process is \(O(n\log n)\): for any segment corresponding to a node in the tree, each time it is moved, we either increase its depth by \(1\) or directly delete it from the tree. Both operations cost \(O(1)\), and each node's depth is at most \(O(\log n)\), hence the complexity as above.

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) {  // Involves merging multiple Li Chao Segment Trees, using dynamic 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;
}

Exercises

「JSOI2008」Blue Mary Opens a Company

「CodeChef」TSUM2 Sum on Tree

「USACO13MAR」Hill Walk G

「CF932F」Escape Through Leaf

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用