DSA DSA In Depth
0%
From-Scratch Build

Li Chao Segment Tree & Monotonic Convex Hull Trick DP Engine

A dynamically allocated Li Chao Segment Tree and a Monotonic Convex Hull Trick queue for optimizing O(n^2) dynamic programming recurrences of the form dp[i] = min_j (m_j * x_i + b_j) to O(n log X) and O(n).

~50 min Advanced Lessons: Build Lab: Dynamic Li Chao Tree & Monotonic Convex Hull Trick Optimizer, Convex Hull Trick (CHT) & Li Chao Segment Tree: Optimizing dp[i] = min_j (m_j x_i + b_j), Segment Trees over Monoids: Recursive vs Iterative (ZKW) Bottom-Up Implementation, Dynamic (Sparse) & Persistent Segment Trees: K-th Smallest in Subarray in O(log N), Monotonic Deques: O(N) Sliding Window Minimum/Maximum, 2D Convex Hull: Graham Scan vs Andrew's Monotone Chain & Rotating Calipers
Interactive Build Lab 0/4 Steps Completed

Code & Verify in the Browser Workbench

Complete 4 progressive engineering steps in JavaScript or TypeScript against an in-browser Node.js v22 runtime (virtual filesystem, loopback TCP/HTTP, and automated unit tests) — zero local setup required.

##Algebraic Reduction of Quadratic DP to Lower Envelope of Lines

Consider the classic frog/partition DP recurrence: $$\text{dp}[i] = C + \min_{j < i} \left( (x_i - x_j)^2 + \text{dp}[j] \right)$$ Expanding $(x_i - x_j)^2 = x_i^2 - 2 x_j x_i + x_j^2$ separates the $i$-only and $j$-only terms from the bilinear cross term:

$$\text{dp}[i] = (x_i^2 + C) + \min_{j < i} \Big( \underbrace{(-2 x_j)}_{m_j} \cdot x_i + \underbrace{(x_j^2 + \text{dp}[j])}_{b_j} \Big)$$

Each state $j$ defines a line $y = m_j x + b_j$, and computing $\text{dp}[i]$ is simply evaluating the lower envelope of all previous lines at $x = x_i$!

Why Li Chao Trees Need Only One Recursive Call Per Level

Two non-parallel lines intersect at at most one point. Suppose at interval $[l, r]$ with midpoint $M$, line $L_{\text{win}}$ is lower than $L_{\text{lose}}$ at $x = M$. Then $L_{\text{lose}}$ can cross below $L_{\text{win}}$ on $[l, M]$ or on $[M+1, r]$, never both!

By storing $L_{\text{win}}$ at the current segment-tree node and pushing $L_{\text{lose}}$ into the single sub-interval where it crosses below $L_{\text{win}}$, every addLine and query visits at most $O(\log(\text{maxX} - \text{minX}))$ nodes—even when slopes and query points arrive in completely arbitrary order.

Curriculum Connections

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Midpoint Dominance Swap in Li Chao Tree

  • Core Mechanical Concept: Midpoint Dominance Swap in Li Chao Tree
  • Target Module: index.js (Step1)
  • Engineering Specification: At interval $[l, r]$ with midpoint $mid$, evaluate both newLine and node.line at $l$ and $mid$. If newLine is strictly smaller at $mid$, swap node.line and newLine so node.line is always the winner at $mid$.
  • Verification Invariant: verifies Step 1: Midpoint Dominance Swap in Li Chao Tree

Step 2: Single-Branch Intersection Recursion

  • Core Mechanical Concept: Single-Branch Intersection Recursion
  • Target Module: index.js (Step2)
  • Engineering Specification: Because two distinct lines intersect at most once, the losing line at $mid$ can beat node.line on at most one half of $[l, r]$ (the left half iff leftBetter !== midBetter). Recurse only into that half in $O(\log X)$ time.
  • Verification Invariant: verifies Step 2: Single-Branch Intersection Recursion

Step 3: Root-to-Leaf Envelope Evaluation

  • Core Mechanical Concept: Root-to-Leaf Envelope Evaluation
  • Target Module: index.js (Step3)
  • Engineering Specification: Implement query(x) by taking the minimum of node.line.eval(x) across all $O(\log X)$ nodes on the path covering $x$.
  • Verification Invariant: verifies Step 3: Root-to-Leaf Envelope Evaluation

Step 4: O(n) Monotonic Deque Convex Hull Trick

  • Core Mechanical Concept: O(n) Monotonic Deque Convex Hull Trick
  • Target Module: index.js (Step4)
  • Engineering Specification: When slopes $m_j$ decrease monotonically and queries $x_i$ increase monotonically, maintain the lower envelope in a deque using cross-multiplied intersection comparisons and a monotone pointer.
  • Verification Invariant: verifies Step 4: O(n) Monotonic Deque Convex Hull Trick

Asymptotic & Memory Layout Guarantees

  • Category: Dynamic Programming & Divide-and-Conquer
  • Difficulty: Advanced (~50 minutes)
  • Key Architectural Highlights:
    • Dynamic Li Chao Segment Tree handling arbitrary (non-monotonic) slopes and query points in O(log X)
    • Single-intersection line dominance invariant recursing into at most one child per level
    • O(n) Monotonic Deque Convex Hull Trick for sorted slopes and queries
  • Tags & Primitives: Li Chao Tree, Convex Hull Trick, DP Optimization, Lower Envelope, Dynamic Allocation

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.