In this article, we discuss the Li Chao tree, a segment tree which can be persistent and is faster in practice compared to the convex hull trick.

Table of contents:

1. Segment trees
2. Convex hull trick
3. Li chao tree
4. Insert operation in Li chao tree
5. Query in Li chao tree
6. Problems using Li chao tree

Pre-requisites:

• Range minimum query
• Segment trees
• Convex Hull Trick

Before we get started, we discuss some prerequisite concepts we have to be familiar with. These are short summaries enough to give a background on Li chao trees, it is advisable to understand these concepts in depth so we have provided references in the references section.

Segment trees

A segment tree is a binary tree used to store intervals or segments, that is, each node in the segment tree represents an interval.

It allows answering range queries over an array effectively while still being flexible to allow modification of the array.

It can solve problems such as finding the sum of consecutive array elements arr[l,...,r] or finding the minimum element in such a range(Range minimum query) in O(logn) time.

Segment trees support the following operations.

We first create/build the structure of the segment tree and initialize it.

1. Update: Updates the element of the array A and reflect corresponding changes to the segment tree.
2. Query: Query an interval or segment and return the answer to the problem
   You can learn more on the links provided at the end of this article.

Applications:

1. Finding the range sum / product, range max / min, prefix sum/ product.
2. Static and dynamic range minimum query.
3. Find perimeter of a set of rectangles on a plane.
4. List all rectilinear line segments intersecting at a query line segment on a plane.

Convex hull trick

This is a technique to efficiently determine which members of a set of linear functions in one variable attains an extremal value for a given value of the independent variable.

In other words, it finds the maximum or minimum value of several convex functions at given points.

It works for the following recurrences

• dp[i] = min{dp[j] + b[j] * a[i]}
• (b[j] ≥ b[j+1]) or (a[i] ≤ a[i+1])

An example

There are n cities.

You want to travel from city 1 to n by car.
You have to buy gasoline.

A liter of gasoline costs $\cos {\mathrm{t}}_{\mathrm{k}}$ in the ${\mathrm{k}}^{\mathrm{th}}$ city.
Your fuel tank is initially empty and you spend 1 liter of gasoline per kilometer.
Cities are located on the same line in ascending order with the ${\mathrm{k}}^{\mathrm{th}}$ city having coordinate ${\mathrm{x}}_{\mathrm{k}}$.

Additionally you have to pay ${\mathrm{toll}}_{\mathrm{k}}$ to enter ${\mathrm{k}}^{\mathrm{th}}$ city.
You are required to make the trip with the minimal possible costs.

Approach.

As you can see we have an optimal substructure and overlapping subproblems(dynamic programming).

Therefore we have the following recurrence;

${\mathrm{dp}}_{\mathrm{i}}={\mathrm{toll}}_{\mathrm{i}}+\min (cos{\mathrm{t}}_{\mathrm{j}}·({\mathrm{x}}_{\mathrm{i}}-{\mathrm{x}}_{\mathrm{j}})+{\mathrm{dp}}_{\mathrm{j}})$

A naive approach would yield O(${\mathrm{n}}^2$) time complexity which is not optimal.
An optimal approach involves using convex hull trick to achieve a O(nlogn) time complexity.

Using convex hull trick

The idea is to maintain a lower convex hull of points (k;b) on a plane such that we have to find the point which has the least dot product with a given point (x;1), that is, for this point, kx+b is minimized.
Such a minimum will be on the lower convex envelope of these points as shown below.

Li chao tree

This is a data structure used to maintain the relationship between line segments on a plane(Cartesian coordinate system).
Li chao line segment tree maintains the 'most dominant line segment' of each interval, that is, the highest line segment at the midpoint of each interval.
We can also define it as a dynamic segment tree with a line in each node.
The root node defines a range from 0 to max.
At each node we store the most dominant line segment.

We maintain the following invariant

The candidates for the answer for a certain x are the nodes on the path from the x to the root, that is, the optimal line for every x will be on the path from x to the root.

Note: Li chao trees can be made persistent and are faster compared to the convex hull trick in practice.

definition: A function has a transcending property if,given two functions f(x), g(x). If f(t) is greater than/smaller that g(t) for some x = t, then f(x) will be greater than / smaller than g(x) for x > t.
In other words, once f(x) "win/lose" g(x), f(x) will continue to "win/lose" g(x).

Li chao trees solves problems with the following structure;

Given a set S containing functions with a transcending property of the same type e,g; (lines, y = ax + b).

We need to handle two types of queries;
1: Add a function to set S.
2: Answer the maximum or minimum value at x = t considering all functions in S.

Insert operation in Li chao tree

To add lines we check the current node, if the line at current node is worse than the new line depending on mid, swap the two lines.
Depending on the evaluation of the two lines on the left point, proceed to the left child or right child.
We always keep the line with greater value at mid and add the other line to the left or right side.
We have the following cases;

Case 1.

newLine > current line for x ∈ (L, mid)

Case 2.

Case 3.
newLine > current line for x ∈ (mid, R)

Case 4.

Case 5.

Steps.

Given a node and coefficients of a line a, b, we want to insert to tree.
We take the following steps;

If node is null, we return a new node with the new line.
We initialize the intervals and the mid values.
We make a comparison between the current line and line in the tree, if current is better we swap the two lines, otherwise we keep it.
We compare the left values for both lines, if greater we go to the left child otherwise we go to the right child.

Pesudocode

insert(node, a, b){
    if(node == NULL)
        return new Node(a, b);
    
    L, R = node.interval;
    int mid = (L + R) / 2
    
    if(a * mid + b > node.line.a * mid + node.line.b)
        swap((a, b), node.line);
    
    if(a * L + b > node.line.a * L + node.line.b)
        node.left = insert(node.left, (a, b))
    else
        node.right = insert(node.right, (a, b));
    return node;
}

Analysis.

The time complexity is O(log C) where C is the size of the range being maintained.

Query in Li chao tree

Candidates for an answer to a query lie on the path from x to the root.
If x is less than mid, we traverse left otherwise we traverse right.

We recursively perform the above steps until we arrive at an empty node or leaf node.

Query function takes the root and x in the query.
If root is null we terminate and return -Infinity.

We then initialize the current interval from left to right.
We initialize mid.

If x is less than the mid, we get the maximum of the query to the left side of the tree otherwise we do the same for the right subtree.

Pseudocode

query(node, x){
    if(node == NULL)
        return -Infinity
    L, R = node.interval;
    mid = l + R / 2
    if(x <= mid)
        return max(query(node.left, x), node.line.a * x + node.line.b);
    else
        return max(query(node.right, x), node.line.a * x + node.line.b);
}

Analysis.

The time complexity is O(logC) because we pass O(logC) nodes.

Problems using Li chao tree

Polynomials

Given n functions yi(x) = ${\mathrm{a}}_0+{\mathrm{a}}_1\mathrm{x}+{\mathrm{a}}_2{\mathrm{x}}^2+{\mathrm{a}}_3{\mathrm{x}}^3$ and q queries. For each query, you are given an integer t and you are required to find out ${\mathrm{y}}_{\mathrm{i}}$ (i ≤ i ≤ n) that minimizes the value of ${\mathrm{y}}_{\mathrm{i}}$(t).

Approach

The range of the query is [0, ${10}^5$]. Using li chao tree we can maintain x = [0, sqrt(${\mathrm{a}}_0$)] directly and maintain x = sqrt(${\mathrm{a}}_0$) + 1, ${10}^5$].

Escape through leaf

Given a tree with n nodes (1 to n) rooted at node 1. Each node has two values associated with it. The values for i-th node are ${\mathrm{a}}_{\mathrm{i}}$ and ${\mathrm{b}}_{\mathrm{i}}$.
One can jump to any node in its subtree. The cost of a jump from node x to node y is the product od ${\mathrm{a}}_{\mathrm{x}}$ and ${\mathrm{b}}_{\mathrm{x}}$. The total cost of a path formed by one or more jumps is the sum of costs of individual jumps.

For every node caclulate the minimum total cost to reach any leaf from the root node.

Note: root can never be a leaf, even if its degree is 1.

Approach.

We are finding the maximum value x = ${\mathrm{a}}_{\mathrm{u}}$ among all lines formed by the nodes in its subtree.
Therefore we build a li chao tree for every node and merge it to its parent.

With this article at OpenGenus, you must have the complete idea of Li Chao Tree.