Convex Hull Trick | Li Chao Tree | Notes

Recently, I encountered a problem in a LeetCode contest that I couldn't solve, so I decided to dig deeper into these patterns. While learning about the Convex Hull Trick, I took some notes and thought of sharing them with the community, as I couldn't find many good posts on this topic.

Please let me know if any statement or code is incorrect—I'll be happy to update it. I'll also be adding few new images soon. If you find this helpful, please consider upvoting; it’ll motivate me to spend more time sharing clean and well-organized notes.

Convex Hull Trick (CHT)

Dynamic Programming is powerful, but sometimes it's not fast enough for large constraints. When your recurrence involves minimizing or maximizing over linear functions, Convex Hull Trick can bring your solution from TLE to AC.
It is a technique used to optimize a certain class of DP problems that involve the minimum (or maximum) of linear functions.

Convex Hull

Imagine you have a set of points on a 2D plane. The convex hull is the smallest convex polygon that encloses all these points — like stretching a rubber band around the outermost points. It captures the "outline" of the shape formed by the points.

How Geometry Helps in Dynamic Programming?

At first glance, geometry and dynamic programming seem like different worlds — one deals with shapes, the other with states and transitions. But geometry helps optimize DP when your recurrence has a linear structure.

Suppose your DP looks like:

dp[i] = min(dp[j] + cost[j] * x[i])  for j < i

Here, for each i, you're trying to find the minimum value of a set of linear functions:
$f_{j} (x)$ = cost[j]* $x_{i}$ + dp[j]

This is where the geometry kicks in:

Each $f_{j} (x)$ is a straight line in the 2D plane.

For a given $x_{i}$ = x[i], you want to find the line with the smallest y value — in other words, the lower envelope of all lines at a specific x-coordinate.

The problem reduces to finding the minimum y-value among all lines at a particular x, which is a classic geometry problem.

This is what the Convex Hull Trick optimizes:

You maintain the optimal (lower/upper) convex hull of all lines.
You efficiently find the one that gives the minimum value at a given x.

So instead of brute-force checking all j, you cleverly use the geometry to prune unnecessary comparisons.

Why This Works

The magic lies in convexity:

If the cost functions are linear and ordered (like monotonic slopes), then the optimal function at each point will appear in a convex order — just like points on a convex hull.
This structure allows for fast insertion and queries, sometimes even in amortized constant time.

Lets try to solve the following problem

Problem: Minimum Cost Road Trip

You are given n cities located along a straight road. The k-th city is located at coordinate xₖ, and the cities are arranged such that x₁ < x₂ < ... < xₙ.

You start your journey in city 1 and aim to reach city n. Your car initially has an empty fuel tank, and it consumes 1 liter of gasoline per kilometer. At each city, you may purchase any amount of gasoline. The cost per liter of gasoline in the k-th city is given by costₖ.

Additionally, to enter any city k, you are required to pay a toll tollₖ.

Your goal is to determine the minimum possible total cost of traveling from city 1 to city n, including fuel purchases and tolls.

Input:
An integer n — the number of cities.
Arrays x[1..n], cost[1..n], and toll[1..n]:
$x_{k}$ : position of the $k^{t h}$ city.
$cos t_{k}$ : cost per liter of fuel in the $k^{t h}$ city.
$t o l l_{k}$ : toll fee to enter the $k^{t h}$ city.

Constraints:
1 ≤ n ≤ $1 0^{5}$
0 ≤ x₁ < x₂ < ... < xₙ ≤ $1 0^{5}$
1 ≤ $cos t_{k}$ , $t o l l_{k}$ ≤ $1 0^{5}$

Output:
The minimum total cost to travel from city 1 to city n.

Naive approach solution using DP

Dynamic Programming Formulation:
Intuition:

You're considering traveling from some earlier city j to the current city
You pay the cost to reach j (dp[j]), buy enough fuel to cover the distance xᵢ - xⱼ at costⱼ per liter, and pay tollᵢ upon entering city i.

Let dp[i] represent the minimum cost to reach the $i^{t h}$ city. We can define the recurrence as:

$d p [i] = j < i min (d p [j] + cos t_{j} \cdot (x_{i} - x_{j}) + t o l l_{i})$

public int minCost(int[] x, int[] cost, int[] toll) {
    int n = x.length;
    int[] dp = new int[n];
    dp[0] = toll[0]; // Starting at city 1
    for (int i = 1; i < n; i++) {
        dp[i] = Integer.MAX_VALUE;
        for (int j = 0; j < i; j++) {
            int fuelCost = (x[i] - x[j]) * cost[j];
            dp[i] = Math.min(dp[i], dp[j] + fuelCost + toll[i]);
        }
    }
    return dp[n - 1]; // cost to reach city n
 }

Naive approach will give you $O (n^{2})$ complexity which will mostly not give TLE for values <= $1 0^{4}$ but it will give TLE for $1 0^{5}$

Transitioning from DP to Convex Hull Trick

We now have the dynamic programming recurrence:
$d p [i] = j < i min (d p [j] + cos t_{j} \cdot (x_{i} - x_{j}) + t o l l_{i})$

We can rearrange the equation to isolate terms that depend on j and i:
$d p [i] = j < i min (cos t_{j} \cdot x_{i} + (d p [j] - cos t_{j} \cdot x_{j})) + t o l l_{i}$

Now, observe this carefully: for a fixed j, this expression is linear with respect to $x_{i}$ — the term $cos t_{j} * x_{i}$ is linear, and the rest is constant for each j.

This means we are trying to compute the minimum value among several lines (functions of $x_{i}$ ) defined as:
$f_{j} (x) = cos t_{j} \cdot x + (d p [j] - cos t_{j} \cdot x_{j})$
which is equivalent to y = mx + c
Where:

The slope of the line is $m = cos t_{j}$
The y-intercept is $c = (d p [j] - cos t_{j} * x_{j})$

So for each i, the value dp[i] becomes:
$d p [i] = min_{j} f_{j} (x_{i}) + t o l l_{i}$

This structure is exactly what the Convex Hull Trick is designed to optimize:

Maintain a set of lines and efficiently query the minimum value at a given x.

CHT (Convex Hull Trick)

We have 3 possible cases

Case 1: Both slopes & queries monotonic

Use list or deque and remove lines as you move forward.
TC: $O (1)$
Solution TC - $O (N + Q)$ if N lines are inserted and Q queries are made.

Lets create a Line class or record to store a line object

// Represents a line: y = m * x + c
record Line (long slope, long intercept){
    public long evaluate(long x) {
        return slope * x + intercept;
    }
}

// Returns x-coordinate of intersection between two lines
private double intersectionX(Line line1, Line line2) {
    return (double) (line2.intercept - line1.intercept) / (line1.slope - line2.slope);
}

evaluate(long x): Computes y for the given x
intersectionX(Line other): Computes the x-coordinate of the intersection point between two lines. Used to maintain convexity of the hull.

How we derive intersectionX()

Suppose we have two lines:
$y_{1} = m_{1} \cdot x + c_{1}$
$y_{2} = m_{2} \cdot x + c_{2}$
At the point of intersection:
$y_{1} = y_{2}$
$=> m_{1} \cdot x + c_{1} = m_{2} \cdot x + c_{2}$
$=> (m_{1} - m_{2}) \cdot = c_{2} - c_{1}$
$=> x = \frac{c _{2} - c _{1}}{m _{1} - m _{2}}$

We have two other important methods:
addLine(Line newLine) and query(long x) along with a pointer for efficent queries.

// Store lines in the convex hull as mx + c
private final List<Line> hull = new ArrayList<>();

// Pointer for efficient queries
private int pointer = 0;

Note: We are not using a deque in this implementation, unlike many C++ implementations you may find online. This helps us avoid the complexity of managing (adding/removing) lines in addLine() and query().

Step 1: addLine(newLine)

The method maintains a lower convex hull of lines (for minimum queries).
It ensures:

The hull keeps only lines that are useful.
If a new line makes a previous line redundant, it's removed.
Redundancy check is based on intersection X-coordinates — if the new line intersects earlier than the last line, the last one becomes useless.

// Add a new line to the convex hull (only if it's not dominated)
public void addLine(Line newLine) {
    while (hull.size() >= 2) {
        Line last = hull.get(hull.size() - 1);
        Line secondLast = hull.get(hull.size() - 2);
        // If newLine makes last line redundant, remove last line
        if (intersectionX(secondLast, newLine) <= intersectionX(secondLast, last)) {
            hull.remove(hull.size() - 1);
        } else {
            break;
        }
    }
    hull.add(newLine);
}

Lets try to add the following lines where lines are sorted in decreasing order of slopes.

L0: y = 3x + 10
L1: y = 2x + 20
L2: y = 1x + 50
L3: y = 0.9x + 45

Lets try to add the lines

For L0

The hull is empty, so we just add L0.
hull = [L0]

For L1

hull.size() = 1 → less than 2, so no redundancy check.
Simply add L1.
hull = [L0, L1]

For L2

hull.size() = 2, so we check redundancy:
- secondLast = L0, last = L1, newLine = L2
- Check if the intersection of (L0, L2) is to the left of the intersection of (L0, L1)
- if intersectionX(L0, L2) <= intersectionX(L0, L1)
  → 20 <= 10 → false → L2 is not redundant
- don't remove L1
- So, we add L2
hull = [L0, L1, L2], highlighted with yellow color.

For L3

hull.size() = 3, so we check redundancy:
1. secondLast = L1, last = L2, newLine = L3
  - Check if the intersection of (L1, L3) is to the left of the intersection of (L1, L2)
  - if intersectionX(L1, L3) <= intersectionX(L1, L2)
    → 22.73 <= 30 → true → L2 is redundant
  - So, we remove L2 because L3 will yield lower values for every x after the intersection point of L1 and L3
2. Now, hull = [L0, L1]
  - secondLast = L0, last = L1, newLine = L3
  - Check if the intersection of (L0, L3) is to the left of the intersection of (L0, L1)
  - if intersectionX(L0, L3) <= intersectionX(L0, L1)
    → 16.67 <= 10 → false → L3 is not redundant
  - don't remove L1
  - So, we add L3
hull = [L0, L1, L3]
The final convex hull consists of the lines L0, L1, and L3, which are visually represented in yellow (from the left up to X0) and continue along the dashed orange line after X0. This dashed orange segment indicates that L2 is no longer part of the convex hull—it was removed because it is completely dominated by L3 beyond the intersection point with L1.

If slope are sorted in increasing order, you can modify the logic of addLine() or you can negate the slope which has the effect of mirroring lines abount y axis, so you can use the same implemenation for both.

Step 2: query(x)

query(x) returns the minimum value of $y = m \cdot x + c$ among all lines currently in the convex hull for the given input x.
It uses a sliding (monotonic) pointer to move through the lines efficiently, giving an amortized $O (1)$ time per query.
This approach is helpful when queries are made for monotonically increasing or decreasing(need changes in query(x)) x.

// Query method using pointer (assumes monotonic queries)
public long query(long x) {
    if (hull.isEmpty()) return Integer.MAX_VALUE;
    // Ensures the pointer stays in bounds for the last line.
    if (pointer >= hull.size()){
        pointer = hull.size() - 1;
    }
    // Move pointer forward if next line gives a smaller value at x
    while (pointer < hull.size() - 1 &&
            hull.get(pointer + 1).evaluate(x) < hull.get(pointer).evaluate(x)) {
        pointer++;
    }
    return hull.get(pointer).evaluate(x);
}

Complete code:

// Convex Hull Trick for dynamic programming optimization
class ConvexHullTrick {
    // Store lines in the convex hull as mx + c
    private final List<Line> hull = new ArrayList<>();

    // Pointer for efficient queries
    private int pointer = 0;

    // Returns x-coordinate of intersection between two lines
    private double intersectionX(Line line1, Line line2) {
        return (double) (line2.intercept - line1.intercept) / (line1.slope - line2.slope);
    }

    // Add a new line to the convex hull (only if it's not dominated)
    public void addLine(Line newLine) {
        while (hull.size() >= 2) {
            Line last = hull.get(hull.size() - 1);
            Line secondLast = hull.get(hull.size() - 2);

            // If newLine makes last line redundant, remove last line
            if (intersectionX(secondLast, newLine) <= intersectionX(secondLast, last)) {
                hull.remove(hull.size() - 1);
            } else {
                break;
            }
        }
        hull.add(newLine);
    }

    // Get minimum y-value at x among all lines in hull
    public long query(long x) {
        if (hull.isEmpty()) return Integer.MAX_VALUE;
        // Ensures the pointer stays in bounds for the last line.
        if (pointer >= hull.size()){
            pointer = hull.size() - 1;
        }
        // Move pointer forward if next line gives a smaller value at x
        while (pointer < hull.size() - 1 &&
                hull.get(pointer + 1).evaluate(x) < hull.get(pointer).evaluate(x)) {
            pointer++;
        }
        return hull.get(pointer).evaluate(x);
    }

    // query method using binary search for non-monotonic queries)
    public long queryBinary(long x) {
        if (hull.isEmpty()) return Integer.MAX_VALUE;
        int lo = 0, hi = hull.size() - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            // Compare intersection of hull[mid] and hull[mid+1] with x
            if (intersectionX(hull.get(mid), hull.get(mid + 1)) < x) {
                lo = mid +1;
            } else {
                hi = mid ;
            }
        }
        return hull.get(lo).evaluate(x);
    }
}

Case 2: Monotonic slopes, non-monotonic queries

Use binary search
TC - queryBinary() : $O (l o g N)$
Solution TC - $O (N + Ql o g N)$ if N lines are inserted and Q queries are made.

// query method using binary search for non-monotonic queries)
public long queryBinary(long x) {
    if (hull.isEmpty()) return Integer.MAX_VALUE;
    int lo = 0, hi = hull.size() - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        // Compare intersection of hull[mid] and hull[mid+1] with x
        if (intersectionX(hull.get(mid), hull.get(mid + 1)) < x) {
            lo = mid +1;
        } else {
            hi = mid ;
        }
    }
    return hull.get(lo).evaluate(x);
}

Case 3: No speical properties (Li Chao Tree)

Use advanced data structures like Li Chao Tree
TC for query() - $O (l o g n)$
Solution TC - $O ((N + Q) . l o g K)$ if N lines are inserted, Q queries are made and K is range of the segment tree.

Li Chao Tree

Prerequisite: Understanding of Segment Trees

Li Chao Tree builds on the idea of a segment tree. Instead of storing a number at each node, we store a line in the form y = mx + c (slope m, intercept c).
It is used to maintain a dynamic set of linear functions and efficiently answer queries of the form:

For a given x, what is the optimal (minimum or maximum) value of all functions f(x) = mx + c in the set?
The tree covers a range from 0 to a maximum x (or from some minimum to maximum x), which can be compressed if all x-values are known in advance.
For every x queried, the optimal line is guaranteed to be stored in one of the nodes along the path from the leaf corresponding to x to the root. This property allows the query to simply traverse that path and take the optimal value.
Each node of the tree represents an interval [L, R] and stores the currently best (dominating) line for that interval.
Important: If the x-range [L, R] is very large (e.g., [-1e9, 1e9]), do not allocate a full array. Instead, use a dynamic tree (like a binary tree) to lazily create nodes only as needed.

class LiChaoTree {
    // stores segment tree
    private Line[] tree;
    private int minX, maxX;

    // Initialize LiChao Tree with a given x-range [minX, maxX]
    public LiChaoTree(int minX, int maxX) {
        this.minX = minX;
        this.maxX = maxX;
        // Allocate enough space for the segment tree (4 * number of discrete x values)
        int size = 4 * (maxX - minX + 1);
        this.tree = new Line[size];
    }
    // methods...
}

addLine(newLine)

When adding a new line to the tree, the algorithm ensures that every node continues to hold the line that is optimal at its midpoint. This is done via a recursive update and possible swapping.

Lets try to insert newLine in the tree. We have the following 5 major cases.

// if newLine is better on left
boolean leftBetter = newLine.evaluate(left) < tree[index].evaluate(left);
// if newline is better on mid
boolean midBetter = newLine.evaluate(mid) < tree[index].evaluate(mid);

Case 1: New line is better on left only

leftBetter = true and midBetter = false

Since newLine is better only on the left, but worse or equal at the midpoint:
- We do not swap.
- We recurse with newLine into the left child [left, mid].
Interpretation: The new line might give the min value in the left subinterval, but not at the midpoint, so we keep the better one at mid in the current node and check the left side.

Case 2: New line is better on mid only

leftBetter = false and midBetter = true

Since newLine is better at mid, we swap it with the current line.
After swapping, the original line (now newLine) might still be better on the right side, so We recurse with it into the right child [mid+1,right]
Interpretation: We place the better line at mid in the node, then try to push the worse one into the subtree where it might still help.

Case 3: New line is better on mid and left

leftBetter = true and midBetter = true

newLine is strictly better at both points, so it must be better somewhere in the interval.
It is better at mid, so we swap the current with newLine.
After swapping, the original line (now newLine) might still be better on the right side, so we recurse with it into the right child [mid+1, right]:
Interpretation: Replace the current line (since it’s worse) and push it into a region where it might still dominate.

Case 4: New line is worse on mid and left

leftBetter = false and midBetter = false

Since newLine is not better on the left and the mid point
- We do not swap.
- We recurse with newLine into the right child [mid+1, right].
Interpretation: The new line might give the min value in the right subinterval, but not at left interval or the midpoint, so we keep the better one at mid in the current node and check the right side.

Case 5: New line is worse everywhere

Early return: The new line is never better, so we discard it.
No swap, no recursion.
Interpretation: This line contributes nothing to the minimum envelope.

private void addLine(Line newLine, int index, int left, int right) {
    int mid = (left + right) / 2;
    // If no line is stored here, insert the new line.
    if (tree[index] == null) {
        tree[index] = newLine;
        return;
    }

    // Early termination:
    // If newLine is not better than the stored line at both endpoints,
    // then it will never be the minimum in [left, right].
    if (newLine.evaluate(left) >= tree[index].evaluate(left) &&
            newLine.evaluate(right) >= tree[index].evaluate(right)) {
        return;
    }

    // Determine whether newLine is better at the left endpoint and the mid point.
    boolean leftBetter = newLine.evaluate(left) < tree[index].evaluate(left);
    boolean midBetter = newLine.evaluate(mid) < tree[index].evaluate(mid);

    // If newLine is better at mid, swap it with the current line.
    if (midBetter) {
        Line temp = tree[index];
        tree[index] = newLine;
        newLine = temp;
    }

    // If this is a leaf node, nothing more to do.
    if (left == right)
        return;

    // Depending on where newLine is better, recursively update the left or right half.
    if (leftBetter != midBetter) {
        addLine(newLine, 2 * index + 1, left, mid);
    } else {
        addLine(newLine, 2 * index + 2, mid + 1, right);
    }
}

query(x)

The query operation runs in $O (l o g K)$ time where K is the size of the x-coordinate range (or $O (l o g N)$ after coordinate compression).

private long query(int x, int index, int left, int right) {
    if (index >= tree.length || tree[index] == null) {
        return Long.MAX_VALUE;
    }
    int mid = (left + right) / 2;
    long current = tree[index].evaluate(x);
    if (left == right)
        return current;
    if (x <= mid) {
        //since we are using mid = (left + right)/2, so x <= mid
        return Math.min(current, query(x, 2 * index + 1, left, mid));
    } else {
        return Math.min(current, query(x, 2 * index + 2, mid + 1, right));
    }
}

Complete Code:

 // LiChaoTree for minimum queries over a given x-range
class LiChaoTree {
    // Stores segment tree
    private Line[] tree;
    private int minX, maxX;

    // Initialize LiChao Tree with a given x-range [minX, maxX]
    public LiChaoTree(int minX, int maxX) {
        this.minX = minX;
        this.maxX = maxX;
        // Allocate enough space for the segment tree (4 * number of discrete x values)
        int size = 4 * (maxX - minX + 1);
        this.tree = new Line[size];
    }

    // Public method to add a new line to the tree
    public void addLine(Line newLine) {
        addLine(newLine, 0, (int) minX, (int) maxX);
    }

    // Recursive method to add a line over the segment [left, right] at tree index
    private void addLine(Line newLine, int index, int left, int right) {
        int mid = (left + right) / 2;
        // If no line is stored here, insert the new line.
        if (tree[index] == null) {
            tree[index] = newLine;
            return;
        }

        // Early termination:
        // If newLine is not better than the stored line at both endpoints,
        // then it will never be the minimum in [left, right].
        if (newLine.evaluate(left) >= tree[index].evaluate(left) &&
                newLine.evaluate(right) >= tree[index].evaluate(right)) {
            return;
        }

        // Determine whether newLine is better at the left endpoint and the mid point.
        boolean leftBetter = newLine.evaluate(left) < tree[index].evaluate(left);
        boolean midBetter = newLine.evaluate(mid) < tree[index].evaluate(mid);

        // If newLine is better at mid, swap it with the current line.
        if (midBetter) {
            Line temp = tree[index];
            tree[index] = newLine;
            newLine = temp;
        }

        // If this is a leaf node, nothing more to do.
        if (left == right)
            return;

        // Depending on where newLine is better, recursively update the left or right half.
        if (leftBetter != midBetter) {
            addLine(newLine, 2 * index + 1, left, mid);
        } else {
            addLine(newLine, 2 * index + 2, mid + 1, right);
        }
    }

    // Query the minimum y-value among all lines at a given x-coordinate.
    public long query(int x) {
        return query(x, 0, minX, maxX);
    }

    // Recursive query method in the segment [left, right] at tree index
    private long query(int x, int index, int left, int right) {
        if (index >= tree.length || tree[index] == null) {
            return Long.MAX_VALUE;
        }
        int mid = (left + right) / 2;
        long current = tree[index].evaluate(x);
        if (left == right)
            return current;
        if (x <= mid) {
            return Math.min(current, query(x, 2 * index + 1, left, mid));
        } else {
            return Math.min(current, query(x, 2 * index + 2, mid + 1, right));
        }
    }
}

Li Chao by building Dynamic Segment Tree

Li Chao Tree that avoids storing the full range — by building a dynamic segment tree using a binary search tree structure where each node corresponds to an interval over the actual x values, but you don’t store all x values ahead of time.
This is useful when:
- You don’t know all x values in advance.
- The x values can be very large (like > 1e5, e.g. [-1e9, 1e9]), but you want to avoid allocating a huge array.

Complete code

public class LiChaoTree {
    // Node class represents a segment of the x-axis [l, r] and stores the best line for that segment.
    private static class Node {
        long l, r; // x-coordinate range
        Line line; // line currently stored at this node
        Node left, right; // children nodes

        public Node(long l, long r, Line line) {
            this.l = l;
            this.r = r;
            this.line = line;
        }
    }

    private Node root;

    // Initialize LiChao Tree with a given x-range [minX, maxX]
    public LiChaoTree(long minX, long maxX) {
        root = new Node(minX, maxX, null);
    }

    // Public method to add a new line to the tree
    public void addLine(Line newLine) {
        addLine(root, newLine);
    }

    // Recursive method to add a line
    private void addLine(Node node, Line newLine) {
        if (node.line == null) {
            // If no line exists at this node, insert the new line here.
            node.line = newLine;
            return;
        }
        long l = node.l;
        long r = node.r;
        long mid = (l + r) / 2;

        // Early termination:
        // If newLine is not better than the stored line at both endpoints,
        // then it will never be the minimum in [left, right].
        if (newLine.evaluate(l) >= node.line.evaluate(l) &&
                newLine.evaluate(r) >= node.line.evaluate(r)) {
            return;
        }

        boolean leftBetter = newLine.evaluate(l) < node.line.evaluate(l);
        boolean midBetter = newLine.evaluate(mid) < node.line.evaluate(mid);

        // For minimum queries, compare the new line and current line at the midpoint.
        if (midBetter) {
            // Swap: keep the better (lower) line at the node.
            Line temp = node.line;
            node.line = newLine;
            newLine = temp;
        }

        // If we are at a leaf node, nothing more to do.
        if (l == r)
            return;

        // Depending on where newLine is better, recursively update the left or right half.
        if (leftBetter != midBetter) {
            if (node.left == null) {
                node.left = new Node(l, mid, null);
            }
            addLine(node.left, newLine);
        }
        // Else if the new line is better on the right segment:
        else {
            if (node.right == null) {
                node.right = new Node(mid + 1, r, null);
            }
            addLine(node.right, newLine);
        }
    }

    // Query the minimum y-value among all lines at a given x-coordinate.
    public long query(long x) {
        return query(root, x);
    }

    // Recursive query method
    private long query(Node node, long x) {
        if (node == null)
            return Long.MAX_VALUE; 
        long curr = (node.line == null ? Long.MAX_VALUE : node.line.evaluate(x));
        long mid = (node.r + node.l) / 2;
        if (x <= mid) {
            return Math.min(curr, query(node.left, x));
        } else {
            return Math.min(curr, query(node.right, x));
        }
    }
}

This reduces the complexity of the solution to $O (n)$ or $O (n l o g n)$ , depending on the structure of the input.

References:
https://cp-algorithms.com/geometry/convex_hull_trick.html
https://codeforces.com/blog/entry/95494
https://codeforces.com/blog/entry/63823
Few youtube videos (don't have the urls collected)

Comments (3)