5.3.7 Li Chao Tree

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

/*

Maintains a dynamic set of lines $y = mx + b$ and answers minimum value queries at integer points.
Lines and queries may arrive in arbitrary order, making this useful for dynamic programming
recurrences of the form $dp(i) = \min_j (m_j x_i + b_j)$ without monotone slopes or query
coordinates.

A Li Chao tree fixes an inclusive coordinate domain $[`lo`, `hi`]$ and stores one line at each node
of a dynamic segment tree. Inserting a line keeps the line that wins at the midpoint and recurses
only into the half where the other line may still win; a query takes the best value along one
root-to-leaf path. Prefer this structure when the domain is known and manageable. The fully dynamic
convex hull in the previous section needs no fixed domain and also supports maximum queries, while a
Li Chao tree has a simpler invariant and is easier to extend to lines active only on subintervals.

No line can be removed once inserted, since a node records only the winner at its midpoint and never
what that line beat. Insertions can instead be undone in reverse order: `add_line()` replaces the
line at O(log d) nodes and creates at most one, so remembering each previous line restores the tree
exactly. Pairing that with a segment tree over the time axis gives arbitrary deletion offline, the
construction that section 4.2.10 applies to a rollback disjoint set.

- `LiChaoTree(lo, hi)` constructs an empty tree over integer domain $[`lo`, `hi`]$.
- `add_line(m, b)` inserts line $y = mx + b$. Lines may be added in any order.
- `query(x)` returns the minimum $y$-value among all inserted lines at coordinate `x`. At least one
  line must have been inserted, and query coordinates may be supplied in any order.
- `snapshot()` returns a token representing the current history size.
- `rollback(snapshot)` undoes all insertions made after `snapshot`.

Overflow warning: each comparison and query evaluates `m * x + b`, which must fit in `int64_t`. The
difference `hi - lo` must also fit in `int64_t`.

Time Complexity:
- O(log d) per call to `add_line()` and `query()`, where $d$ is the distance between `lo` and `hi`.
- O(1) per call to `snapshot()`, and O(log d) per line undone by `rollback()`.

Space Complexity:
- O(n) node storage for $n$ lines inserted, since each insertion creates at most one node.
- O(log d) history per inserted line that has not been rolled back.
- O(log d) auxiliary stack space per operation.

*/

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <memory>
#include <utility>
#include <vector>

const int64_t INF = INT64_MAX / 4;

class LiChaoTree {
  struct Line {
    int64_t m, b;
    explicit Line(int64_t m = 0, int64_t b = INF) : m(m), b(b) {}
    int64_t eval(int64_t x) const { return m * x + b; }  // Overflow warning.
  };

  struct Node {
    Line f;
    std::unique_ptr<Node> left, right;
    explicit Node(const Line &f) : f(f) {}
  };

  // One insertion either replaces a node's line or creates the node, so recording the previous
  // state of each node it touches is enough to restore the tree exactly.
  struct Undo {
    Node *node;                   // Node whose line was replaced, or null if a node was created.
    Line prev;                    // The line that node held before.
    std::unique_ptr<Node> *slot;  // Owner of the created node, when node is null.
    Undo(Node *node, const Line &prev, std::unique_ptr<Node> *slot)
        : node(node), prev(prev), slot(slot) {}
  };

  std::unique_ptr<Node> root;
  int64_t lo, hi;
  std::vector<Undo> trail;

  void add_line(std::unique_ptr<Node> &n, int64_t lo, int64_t hi, Line f) {
    if (n == nullptr) {
      n = std::make_unique<Node>(f);
      trail.emplace_back(nullptr, Line(), &n);
      return;
    }
    int64_t mid = lo + (hi - lo) / 2;
    bool left_better = f.eval(lo) < n->f.eval(lo);
    bool mid_better = f.eval(mid) < n->f.eval(mid);
    if (mid_better) {
      trail.emplace_back(n.get(), n->f, nullptr);
      std::swap(f, n->f);
    }
    if (lo == hi) {
      return;
    }
    if (left_better != mid_better) {
      add_line(n->left, lo, mid, f);
    } else {
      add_line(n->right, mid + 1, hi, f);
    }
  }

  static int64_t query(Node *n, int64_t lo, int64_t hi, int64_t x) {
    if (n == nullptr) {
      return INF;
    }
    int64_t res = n->f.eval(x);
    if (lo == hi) {
      return res;
    }
    int64_t mid = lo + (hi - lo) / 2;
    if (x <= mid) {
      return std::min(res, query(n->left.get(), lo, mid, x));
    }
    return std::min(res, query(n->right.get(), mid + 1, hi, x));
  }

 public:
  LiChaoTree(int64_t lo, int64_t hi) : lo(lo), hi(hi) { assert(lo <= hi); }

  LiChaoTree(const LiChaoTree &) = delete;
  LiChaoTree &operator=(const LiChaoTree &) = delete;
  void add_line(int64_t m, int64_t b) { add_line(root, lo, hi, Line(m, b)); }

  int64_t query(int64_t x) const {
    assert(root != nullptr);
    assert(lo <= x && x <= hi);
    return query(root.get(), lo, hi, x);
  }

  int snapshot() const { return static_cast<int>(trail.size()); }

  void rollback(int snapshot) {
    assert(0 <= snapshot && snapshot <= static_cast<int>(trail.size()));
    while (static_cast<int>(trail.size()) > snapshot) {
      const Undo &u = trail.back();
      if (u.slot != nullptr) {
        u.slot->reset();
      } else {
        u.node->f = u.prev;
      }
      trail.pop_back();
    }
  }
};

/*** Example Usage ***/

#include <cassert>

int main() {
  LiChaoTree h(-10, 10);
  h.add_line(3, 0);
  h.add_line(0, 6);
  h.add_line(1, 2);
  h.add_line(2, 1);
  // Minimize among y = 3x, 6, x + 2, and 2x + 1.
  assert(h.query(0) == 0);
  assert(h.query(2) == 4);
  assert(h.query(1) == 3);
  assert(h.query(3) == 5);

  // Insertions undo in reverse order, which is what makes offline deletion possible.
  int token = h.snapshot();
  h.add_line(-1, -9);
  assert(h.query(3) == -12);
  h.rollback(token);
  assert(h.query(3) == 5);
  return 0;
}