Hello everyone! I discovered a new (?) trick on how to apply lazy propagation on the Li Chao Tree and decided to write a blog about it. I've personally never seen it before (outside of myself), nor have I seen a problem that needs the Extended Li Chao Tree specifically, but it can overkill some problems. Of course, I might not be looking hard enough...

You can learn about the basics of Li Chao Tree from cp-algorithms or this simple blog.

The Extended Li Chao Tree can do the following problems (and other variations):

Problem 1

There is an array $$$A$$$ of size $$$N$$$. There are $$$Q$$$ online operations:

• Range Line Insertion. Given $$$l$$$, $$$r$$$, $$$a$$$, $$$b$$$, do $$$A_i = \max(A_i, a \cdot i + b)$$$, $$$\forall i \in [l, r]$$$ in $$$O(\log^2 N)$$$
• Range Line Addition. Given $$$l$$$, $$$r$$$, $$$a$$$, $$$b$$$, do $$$A_i += a \cdot i + b$$$, $$$\forall i \in [l, r]$$$ in $$$O(\log^2 N)$$$.
• Point Query. Given $$$i$$$, return $$$A_i$$$ in $$$O(\log N)$$$.

Problem 2

There is an array $$$A$$$ of size $$$N$$$. There are $$$Q$$$ online operations:

• Range Line Insertion. Given $$$l$$$, $$$r$$$, $$$a$$$, $$$b$$$, do $$$A_i = \max(A_i, a \cdot i + b)$$$, $$$\forall i \in [l, r]$$$ in $$$O(\log^2 N)$$$
• Range Sum Addition. Given $$$l$$$, $$$r$$$, $$$b$$$, do $$$A_i += b$$$, $$$\forall i \in [l, r]$$$ in $$$O(\log^2 N)$$$.
• Range Maximum Query. Given $$$l$$$, $$$r$$$, return $$$\max\limits_{\forall i \in [l, r]} A_i$$$ in $$$O(\log N)$$$.

Prerequisites

Some things you should know beforehand:

• The Li Chao Tree can work with any functions, as long as that for all pairs of functions $$$f$$$ and $$$g$$$, there is a point $$$p$$$ where $$$f(x) \leq g(x)$$$ for $$$x \leq p$$$ and $$$f(x) \geq g(x)$$$ for $$$x \geq p$$$. However, for this discussion, I will assume that $$$f$$$ is always a line equation $$$f(x) = a \cdot x + b$$$.
• We can also insert a line $$$f(x)$$$ only to a certain range $$$[l, r]$$$. Just as in the usual segment tree, we first split the interval $$$[l, r]$$$ into $$$O(\log N)$$$ segments. After that, we can do the "global" Li Chao Tree insertion on the subtree of those segments.

Example code for a basic version of the Li Chao Tree (with line insertions on a certain range).

template<typename data_t>
struct Line {
  data_t a, b;
  
  Line() : a(0), b(-inf) {}
  Line(data_t a, data_t b) : a(a), b(b) {}
  
  data_t get(data_t x) {
    return a * x + b;
  }
};

struct Node {
  Line<data_t> line = Line<data_t>();
  Node *lc = nullptr;
  Node *rc = nullptr;
};

void InsertLineKnowingly(Node* &n, data_t tl, data_t tr, Line<data_t> x) {
  if (n == nullptr) n = new Node();
  if (n->line.get(tl) < x.get(tl)) swap(n->line, x);
  if (n->line.get(tr) >= x.get(tr)) return;
  if (tl == tr) return;
  data_t mid = (tl + tr) / 2;
  if (n->line.get(mid) > x.get(mid)) {
    InsertLineKnowingly(n->rc, mid + 1, tr, x);
  } else {
    swap(n->line, x);
    InsertLineKnowingly(n->lc, tl, mid, x);
  }
}

void InsertLine(Node* &n, data_t tl, data_t tr, data_t l, data_t r, Line<data_t> x) {
  if (tr < l || r < tl || tl > tr || l > r) return;
  if (n == nullptr) n = new Node();
  if (l <= tl && tr <= r) return InsertLineKnowingly(n, tl, tr, x);
  data_t mid = (tl + tr) / 2;
  InsertLine(n->lc, tl, mid, l, r, x);
  InsertLine(n->rc, mid + 1, tr, l, r, x);
}

data_t Query(Node* &n, data_t tl, data_t tr, data_t x) {
  if (n == nullptr) return -inf;
  if (tl == tr) return n->line.get(x);
  data_t res = n->line.get(x);
  data_t mid = (tl + tr) / 2;
  if (x <= mid) {
    res = max(res, Query(n->lc, tl, mid, x));
  } else {
    res = max(res, Query(n->rc, mid + 1, tr, x));
  }
  return res;
}

void InsertLine(data_t l, data_t r, Line<data_t> x) {
  return InsertLine(root, 0, sz - 1, l, r, x);
}

data_t Query(data_t x) {
  return Query(root, 0, sz - 1, x);
}

The Extension

Let's focus on the Li Chao Tree that solves Problem 1. Range line insertion and point query can be implemented as usual.

Now we need to implement a lazy propagation method. But implementing it naively won't work. As an example, let the current node be $$$[1, N]$$$ with line $$$f$$$, and we want to do a range addition on the interval $$$[2, N - 1]$$$. What happens in a usual segment tree is that we directly recurse to $$$[1, M]$$$ and $$$[M + 1, N]$$$ with $$$M = \lfloor \frac{L + R}{2} \rfloor$$$. But let's say that we do a range sum addition with value $$$-\infty$$$ to the range $$$[2, N - 1]$$$. Since line $$$f$$$ on node $$$[1, N]$$$ is not affected by the update, when we query point $$$x = 2$$$, we will get $$$f(2)$$$ instead of $$$-\infty$$$.

How can we affect $$$f$$$ as well? Since $$$f$$$ must also be affected, then we can just push it downwards. In other words, we do a global line insertion on the intervals $$$[1, M]$$$ and $$$[M + 1, N]$$$ with the line $$$f$$$, then reset $$$[1, N]$$$ to have no line. After that, we can safely recurse to $$$[1, M]$$$ and $$$[M + 1, N]$$$, and all lines which might be optimal on the range $$$[2, N - 1]$$$ will be affected.

Since the global line insertion runs in $$$O(\log N)$$$ time, and we need to traverse $$$O(\log N)$$$ nodes when splitting the update interval, this takes $$$O(\log^2 N)$$$ time.

Example code for the Extended Li Chao Tree.

template<typename data_t>
struct Line {
  data_t a, b;

  Line() : a(0), b(-inf) {}
  Line(data_t a, data_t b) : a(a), b(b) {}

  data_t get(data_t x) {
    return a * x + b;
  }

  void add(Line x) {
    a += x.a;
    b += x.b;
  }
};

struct Node {
  Line<data_t> line = Line<data_t>();
  Line<data_t> lazy = Line<data_t>(0, 0);

  Node *lc = nullptr;
  Node *rc = nullptr;

  void apply(data_t l, data_t r, Line<data_t> v) {
    line.add(v);
    lazy.add(v);
  }
};

void PushLazy(Node* &n, data_t tl, data_t tr) {
  if (n == nullptr) return;
  if (n->lc == nullptr) n->lc = new Node();
  if (n->rc == nullptr) n->rc = new Node();
  data_t mid = (tl + tr) / 2;
  n->lc->apply(tl, mid, n->lazy);
  n->rc->apply(mid + 1, tr, n->lazy);
  n->lazy = Line<data_t>(0, 0);
}

void PushLine(Node* &n, data_t tl, data_t tr) {
  if (n == nullptr) return;
  data_t mid = (tl + tr) / 2;
  InsertLineKnowingly(n->lc, tl, mid, n->line);
  InsertLineKnowingly(n->rc, mid + 1, tr, n->line);
  n->line = Line<data_t>();
}

void InsertLineKnowingly(Node* &n, data_t tl, data_t tr, Line<data_t> x) {
  if (n == nullptr) n = new Node();
  if (n->line.get(tl) < x.get(tl)) swap(n->line, x);
  if (n->line.get(tr) >= x.get(tr)) return;
  if (tl == tr) return;
  data_t mid = (tl + tr) / 2;
  PushLazy(n, tl, tr);
  if (n->line.get(mid) > x.get(mid)) {
    InsertLineKnowingly(n->rc, mid + 1, tr, x);
  } else {
    swap(n->line, x);
    InsertLineKnowingly(n->lc, tl, mid, x);
  }
}

void InsertLine(Node* &n, data_t tl, data_t tr, data_t l, data_t r, Line<data_t> x) {
  if (tr < l || r < tl || tl > tr || l > r) return;
  if (n == nullptr) n = new Node();
  if (l <= tl && tr <= r) return InsertLineKnowingly(n, tl, tr, x);
  data_t mid = (tl + tr) / 2;
  PushLazy(n, tl, tr);
  InsertLine(n->lc, tl, mid, l, r, x);
  InsertLine(n->rc, mid + 1, tr, l, r, x);
}

void AddLine(Node* &n, data_t tl, data_t tr, data_t l, data_t r, Line<data_t> x) {
  if (tr < l || r < tl || tl > tr || l > r) return;
  if (n == nullptr) n = new Node();
  if (l <= tl && tr <= r) return n->apply(tl, tr, x);
  data_t mid = (tl + tr) / 2;
  PushLazy(n, tl, tr);
  PushLine(n, tl, tr);
  AddLine(n->lc, tl, mid, l, r, x);
  AddLine(n->rc, mid + 1, tr, l, r, x);
}

data_t Query(Node* &n, data_t tl, data_t tr, data_t x) {
  if (n == nullptr) return -inf;
  if (tl == tr) return n->line.get(x);
  data_t res = n->line.get(x);
  data_t mid = (tl + tr) / 2;
  PushLazy(n, tl, tr);
  if (x <= mid) {
    res = max(res, Query(n->lc, tl, mid, x));
  } else {
    res = max(res, Query(n->rc, mid + 1, tr, x));
  }
  return res;
}

void InsertLine(data_t l, data_t r, Line<data_t> x) {
  return InsertLine(root, 0, sz - 1, l, r, x);
}

void AddLine(data_t l, data_t r, Line<data_t> x) {
  return AddLine(root, 0, sz - 1, l, r, x);
}

data_t Query(data_t x) {
  return Query(root, 0, sz - 1, x);
}

Problem 2 can be implemented in the same way, except that we store the range maximum as well. Note that we cannot do a range line addition this way (since the optimal $$$x$$$ which yields the maximum value might change). However, it might be possible in another way.

Optimizing Dijkstra in Line Graphs

TROC #13 — Mall and Transportation

Problem. Given a line graph with $$$H$$$ nodes. You can travel from $$$u$$$ to $$$v$$$ in $$$|u - v| \cdot S$$$ time. There are also $$$N$$$ nodes $$$D_1, D_2, ..., D_N$$$, where you can travel from $$$D_u$$$ to any nodes $$$v \in [A_u, B_u]$$$ in $$$|D_u - v| \cdot T_u + Q_u$$$ time. You initially start at $$$D_X$$$ for a given $$$X$$$. Find the minimum time to get to floors $$$D_1, D_2, ..., D_N$$$.

Solution. This is a blatant shortest path problem. Note that for a given $$$t$$$, all nodes reachable in $$$\leq t$$$ time form a segment $$$[l, r]$$$. Thus, after we reached all nodes $$$\in [l, r]$$$, the next node must be either $$$l - 1$$$ or $$$r + 1$$$. Now we only need to be able to update distance quickly. This can be easily done by modeling the update as a line equation insertion, which is solvable using the basic Li Chao Tree.

OII 2020 — Candele

Problem. Given $$$N$$$ segments $$$A_i, B_i$$$.

• If $$$A_i < B_i$$$, then there exist edges $$$(u, u + 1), A_i \leq u < B_i$$$.
• If $$$A_i > B_i$$$, then there exist edges $$$(u, u - 1), B_i < u \leq A_i$$$.

Find the shortest path from $$$A_1$$$ to $$$A_2, A_3, ..., A_N$$$!

Solution. The solution is the same as the previous one. Also, variation 3 is almost exactly the same problem.

For the original problem, since all line equations $$$f(x) = a \cdot x + b$$$ inserted has the property $$$a \in {1, -1}$$$, we can store $$$2$$$ segment trees instead: one for $$$a = 1$$$ and one for $$$a = -1$$$. That way, we can simply maximize $$$b$$$ with a classic segment tree which takes only $$$O(\log N)$$$ time per operation.

Overkilling Data Structure Problems

Singapore NOI 2020 — Progression

Problem. Given an array $$$A$$$ of size $$$N$$$. There are $$$Q$$$ operations:

• Given $$$L$$$, $$$R$$$, $$$S$$$, $$$C$$$, $$$\forall i \in [L, R]$$$ do $$$A_i += S + (i - L) \cdot C$$$.
• Given $$$L$$$, $$$R$$$, $$$S$$$, $$$C$$$, $$$\forall i \in [L, R]$$$ do $$$A_i = S + (i - L) \cdot C$$$.
• Given $$$L$$$, $$$R$$$, find the maximum $$$j - i + 1$$$ where $$$L \leq i \leq j \leq R$$$ and $$$\forall x,y \in [i, j - 1]$$$, $$$A_{x + 1} - A_{x} = A_{y + 1} - A_{y}$$$.

Solution. Operation $$$1$$$ and $$$2$$$ are both supported by an Extended Li Chao Tree, so we can maintain the values of $$$A$$$. To check for operation $$$3$$$, we need to maintain a segment tree of the array $$$B$$$, where $$$B_i = A_i - A_{i-1}$$$.

• For operation $$$1$$$, $$$B_i += C$$$, $$$\forall i \in [L + 1, R]$$$, while $$$B_L$$$ and $$$B_{R + 1}$$$ changes. We can do a range sum addition on the segment tree of $$$B$$$, then easily update $$$B_L$$$ and $$$B_{R + 1}$$$ since we can maintain the values of $$$A$$$.
• For operation $$$2$$$, we set $$$B_i = C$$$, $$$\forall i \in [L + 1, R]$$$. We can do a range set update on the segment tree of $$$B$$$, then update $$$B_L$$$ and $$$B_{R + 1}$$$ accordingly.
• For operation $$$3$$$, we need to find the maximum length subarray of $$$B[L+1 \dots R]$$$ where all elements in that subarray are equal. This is similar to a classic segment tree problem on finding a subsegment with the maximal sum for a given subarray, described at cp-algorithms. We can do a range sum addition and range set update through normal lazy propagation.

ABC177F — I hate Shortest Path Problem

Problem. There is an $$$(H + 1) \times W$$$ grid. We start at any cell on the top row and can move either down or right in a single step. However, for the $$$i$$$-th row, we cannot move downwards for the cells $$$(i, A_i), (i, A_i + 1), \dots, (i, B_i)$$$. Find the minimum steps to reach a cell in the $$$i$$$-th row, $$$\forall i \in [2, H + 1]$$$.

Solution. We can maintain the shortest path for all $$$W$$$ columns of some row $$$i$$$ in an array $$$A$$$ of size $$$W$$$. We can simulate moving from row $$$i$$$ to $$$i + 1$$$ quickly with the following operations:

• Do $$$A_i += 1$$$, $$$\forall i \in [1, W]$$$.
• Do $$$A_i = \infty$$$, $$$\forall i \in [l, r]$$$.
• Do $$$A_i = \min(A_i, a \cdot i + b)$$$, $$$\forall i \in [l, r]$$$.
• Find $$$\min\limits_{\forall i \in [1, W]} A_i$$$.

Everything can be done with an Extended Li Chao Tree.

Naively Maintaining Slope Trick

CF713C — Sonya and Problem Wihtout a Legend

Problem. Given an array $$$A$$$ of size $$$N$$$. In one operation, you can choose any element and increase or decrease it by $$$1$$$. Find the minimum number of operations to make the array strictly increasing.

Solution. See the solution described at:

• [Tutorial] Slope Trick.
• Slope trick explained.

However, instead of using a priority queue to store the slope changing points, you could store the lines themselves with the Extended Li Chao Tree. Since slope trick problems require the function to be convex (or concave), we can ternary search to find the value where the slope is $$$0$$$. Code.

Convex Hull Trick Again

The Extended Li Chao Tree is more powerful than a standard line container, so it can also solve all problems solvable by it (and also trivializes some).

The Motivation Behind

IOI 2018 — Meetings

Problem. Given an array $$$H$$$ of size $$$N$$$. You are given $$$Q$$$ queries $$$[ql, qr]$$$. For each query, find $$$\min\limits_{\forall x \in [ql, qr]}(\sum\limits_{y = ql}^{x-1} \max\limits_{\forall z \in [y, x]} H_z + \sum\limits_{y = x}^{qr} \max\limits_{\forall z \in [x, y]} H_z)$$$.

Solution. First, we build a Cartesian Tree over the array $$$H$$$ (for all comparisons, we use a pair $$$(H_i, i)$$$ to ensure all elements are distinct). Let us assume we are at the node which denotes the segment $$$[L, R]$$$, where the maximum value is $$$(H_M, M)$$$, and its children denotes the segment $$$[L, M - 1]$$$ and $$$[M + 1, R]$$$. All queries on this segment must satisfy $$$L \leq ql \leq M \leq qr \leq R$$$ and $$$\max\limits_{ql \leq i \leq qr} (H_i, i) = (H_M, M)$$$. Consider a query $$$[ql, qr]$$$ on this segment.

Let $$$opt_{l, r}$$$ be the answer for the query $$$[l, r]$$$. Assume we have values $$$opt_{L, M - 1}, opt_{L + 1, M - 1}, \dots, opt_{M - 1, M - 1}$$$ and $$$opt_{L, L}, opt_{L, L + 1}, \dots, opt_{L, M - 1}$$$ from the node $$$[L, M - 1]$$$, and values $$$opt_{M + 1, R}, opt_{M + 2, R}, \dots, opt_{R, R}$$$ and $$$opt_{M + 1, M + 1}$$$, $$$opt_{M + 1, M + 2}$$$, \dots, $$$opt_{M + 1, R}$$$ from the node $$$[M + 1, R]$$$.

If we have such values, for a query $$$[ql, qr]$$$, the answer is $$$\min(opt_{ql, M - 1} + (qr - M + 1) \cdot H_M, opt_{M + 1, qr} + (M - ql + 1) \cdot H_M)$$$. This is true since $$$H_M$$$ is the maximum value on segment $$$[L, R]$$$. Now we only need to calculate $$$opt_{L, L}, opt_{L, L + 1}, \dots, opt_{L, R}$$$ and $$$opt_{L, R}, opt_{L + 1, R}, \dots, opt_{R, R}$$$ and we're done.

Consider $$$opt_{L, L}, opt_{L, L + 1}, \dots, opt_{L, M - 1}$$$ and $$$opt_{M + 1, M + 1}, opt_{M + 1, M + 2}, \dots, opt_{M + 1, R}$$$. Notice that for $$$x \in [M + 1, R]$$$, then $$$opt_{L, x} = \min(opt_{L, M - 1} + (x - M + 1) \cdot H_M, opt_{M + 1, x} + (M - L + 1) \cdot H_M )$$$. The second one is simply pasting $$$opt_{M + 1, x}$$$ to $$$opt_{L, x}$$$ then doing a range sum addition. After that, then we can handle the first part by taking the minimum with $$$opt_{L, M - 1} + (x - M + 1) \cdot H_M$$$. Notice that it is simply a line insertion on the range $$$[M + 1, R]$$$. The same thing can be done for $$$opt_{M + 1, R}, opt_{M + 2, R}, \dots, opt_{R, R}$$$ and $$$opt_{L, M - 1}, opt_{L + 1, M - 1}, \dots, opt_{M - 1, M - 1}$$$.

At first glance, we will need an Extended Li Chao Tree, but you don't actually need to. Since we do the range addition updates in a specific "bottom-up" manner, when traversing a node in the segment tree, we do not have to split the line and do a global insert to its children simply because there is no line yet. Thus we can use a basic Li Chao Tree with normal lazy propagation on top.

This problem is the motivation behind the Extended Li Chao Tree — being able to support the needed operations without any specific constraint.

If you spot any mistakes or errors, please let me know! Feel free to ask any questions, suggest other problems, or share any new tricks you found in the comments. :)