Li Chao Segment Tree

A Li Chao tree maintains a set of linear functions and answers minimum-value queries without ordering the slopes or the queries. Instead of explicitly building every interval of the lower envelope, it stores a line that wins at each node’s midpoint and recursively places a displaced line where it may still matter. This version works on a fixed inclusive INTEGER X domain [low,high]. It is useful for online DP transitions when the monotone Convex Hull Trick assumptions fail.

Prerequisites: Convex Hull Trick line formulation; segment-tree intervals; recursion. Difficulty: Expert. Review: Convex Hull Trick.

Build the idea

1. 1. Use the one-crossing property

   Two distinct linear functions cross at most once. If one line is no worse at both endpoints of an interval, it is no worse throughout. More generally, once the better midpoint line is stored at a node, the other line can beat it only on one side of the midpoint. This property allows insertion to recurse into one child rather than both. Arbitrary nonlinear curves do not automatically satisfy the same assumption.

2. 2. Keep the midpoint winner

   At interval [l,r], compare incoming and stored lines at l and mid. If incoming is better at mid, swap the two; the node now keeps the midpoint winner. The displaced candidate is still worth keeping on the left precisely when the original left and midpoint comparison results differ; otherwise send it right. At a leaf there is no smaller interval. Equal slopes require no recursion: retain only the smaller intercept.

3. 3. Query along one root-to-leaf path

   For an integer x, evaluate every stored line on the path containing x and return their minimum. A line stored at an ancestor might be best at x even if it was chosen for a different midpoint, so returning only the leaf’s value is wrong. A missing child contributes INF. The first insertion populates the root; before any insertion, queries explicitly print EMPTY rather than exposing an infinity sentinel.

4. 4. Trace the sample

   Use domain [−10,10]. Insert y=2x+1 and y=−x+4 in arbitrary slope order. At x=0 their values are 1 and 4, so answer 1. At x=3 the values are 7 and 1, answer 1. Add horizontal y=−2; x=0 now answers −2, and x=5 also chooses −2 over −x+4=−1. At x=10 the sloping line gives −6 and wins. Queries can jump in any order.

5. 5. Fix domain, storage and precision

   The implementation creates child nodes only as needed, using integer indices into a vector. Do not hold references to vector nodes across push_back: reallocation invalidates them. Splitting [l,r] into [l,mid] and [mid+1,r] guarantees termination even for negative endpoints. Queries must stay inside the declared domain. This lesson bounds coordinates and slopes by 10^6 and intercepts by 10^9, keeping evaluation exact in long long; it does not claim arbitrary real-coordinate precision.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<limits>
#include<algorithm>
using namespace std;
using ll=long long;
struct Line{
    ll m=0,b=0;
    ll value(ll x)const{
        return m*x+b;
    }
};
struct Node{
    Line line;
    bool has=false;
    int left=-1,right=-1;
};
vector<Node>tree(1);
void insert(int node,ll l,ll r,Line incoming){
    if(!tree[node].has){
        tree[node].line=incoming;
        tree[node].has=true;
        return;
    }
    if(tree[node].line.m==incoming.m){
        if(incoming.b<tree[node].line.b){
            tree[node].line=incoming;
        }
        return;
    }
    ll mid=l+(r-l)/2;
    bool betterLeft=incoming.value(l)<tree[node].line.value(l);
    bool betterMid=incoming.value(mid)<tree[node].line.value(mid);
    if(betterMid){
        swap(incoming,tree[node].line); // Keep midpoint winner here.
    }
    if(l==r){
        return;
    }
    bool goLeft=betterLeft!=betterMid;
    int child=goLeft?tree[node].left:tree[node].right;
    if(child==-1){
        child=(int)tree.size();
        tree.push_back(Node{});
        // Reallocation may move tree: never retain a Node& across push_back.
        if(goLeft){
            tree[node].left=child;
        }
        else{
            tree[node].right=child;
        }
    }
    if(goLeft){
        insert(child,l,mid,incoming);
    }
    else{
        insert(child,mid+1,r,incoming);
    }
}
ll query(int node,ll l,ll r,ll x){
    const ll INF=numeric_limits<ll>::max()/4;
    if(node==-1){
        return INF;
    }
    ll answer=tree[node].has?tree[node].line.value(x):INF;
    if(l==r){
        return answer;
    }
    ll mid=l+(r-l)/2;
    if(x<=mid){
        return min(answer,query(tree[node].left,l,mid,x));
    }
    return min(answer,query(tree[node].right,mid+1,r,x));
}
int main(){
    ll low,high;
    int q;
    if(!(cin>>low>>high>>q)){
        return 0;
    }
    bool any=false;
    while(q--){
        char type;
        cin>>type;
        if(type=='L'){
            Line line;
            cin>>line.m>>line.b;
            insert(0,low,high,line);
            any=true;
        }
        else{
            ll x;
            cin>>x;
            if(!any){
                cout<<"EMPTY\n";
            }
            else{
                cout<<query(0,low,high,x)<<'\n';
            }
        }
    }
}

Complexity analysis

Let C=high−low+1. Each insertion and query follows O(log C+1) nodes, so q operations cost O(q(log C+1)) time. O(1) initial memory; the sparse implementation allocates at most one previously empty child per insertion, so O(K) nodes for K inserted lines, and O(log C+1) recursion depth. A fully preallocated alternative could use O(C) memory. Bounds are integer, −10^6≤low≤high≤10^6; |m|≤10^6 and |b|≤10^9.

Example input and output

Read integer low high q, then q operations: L m b inserts y=mx+b; Q x asks the minimum at x within [low,high]. Bounds and coefficients satisfy the stated limits. Print EMPTY before any insertion; otherwise print the exact integer minimum.

Input

-10 10 7
L 2 1
L -1 4
Q 0
Q 3
L 0 -2
Q 0
Q 10

Output

1
1
-2
-6

The first two queries choose different sloping lines. The horizontal line wins at zero, while −x+4 still wins at x=10.

Practical applications

Use for online linear-function DP and arbitrary-order line insertions/queries over a known discrete range. Monotonic CHT has better amortized constants when both ordering assumptions hold. If X coordinates are a known sparse set, a coordinate-compressed Li Chao variant can operate on those values. A normal segment tree aggregates stored array elements; Li Chao instead exploits comparisons between functions.

Check your understanding

Why does inserting a displaced line need at most one recursive branch?

Put it into practice

Test a one-coordinate domain, equal slopes, negative X values and queries before insertion.