Solving Convex Hull Trick DP with Dynamic Programming

1. Introduction and Core Concepts

Convex hull trick DP, often abbreviated as CHT DP, is one of the most powerful optimization techniques for dynamic programming in competitive programming and advanced algorithm design. It transforms a naive quadratic DP recurrence into a linear or log-linear solution by recognizing that the transition can be expressed as a set of lines and a query for the minimum or maximum value at a given x-coordinate. When you encounter a DP of the form dp[i] = min(j < i) { m[j] * x[i] + b[j] } + C[i], the convex hull trick is likely the intended optimization.

At its heart, convex hull trick DP exploits geometry. Each previously computed DP state j defines a line y = m[j] * x + b[j] where the slope m[j] and intercept b[j] are derived from dp[j] and input data. Computing dp[i] then reduces to querying the lower envelope (for minimization) or upper envelope (for maximization) of all lines at x = x[i]. The set of lines that can ever be optimal forms a convex hull, hence the name. Irrelevant lines that are never minimal for any x are discarded, drastically reducing work.

Why does convex hull trick dp matter? Without it, many DP problems with N up to 200,000 or even 1,000,000 would be intractable with an O(N^2) solution. With CHT, these same problems become solvable in O(N log N) or O(N) time, enabling real-time systems, large-scale optimization, and efficient resource allocation. It is a canonical example of how a geometric insight can yield an order-of-magnitude algorithmic speedup, and it serves as a gateway to more advanced structures like the Li Chao segment tree and parametric search techniques.

The Fundamental DP Form

Not every DP can be optimized with the convex hull trick. The technique applies only when the recurrence is linear in terms of a query variable. The classic form is dp[i] = min_{j < i} (dp[j] + b[j] * a[i] + c[j] + d[i]), which can be rewritten as dp[i] = min_{j < i} (m[j] * x[i] + b[j]) + C[i]. Here m[j] depends only on j, x[i] depends only on i, and C[i] is an additive term independent of j. If your recurrence contains products of i and j terms like a[i] * b[j], you should immediately consider CHT.

A common example is the DP for partitioning an array with quadratic cost: dp[i] = min_{j < i} dp[j] + (prefix[i] - prefix[j])^2. Expanding the square yields dp[i] = prefix[i]^2 + min_{j < i} (-2*prefix[j] * prefix[i] + dp[j] + prefix[j]^2). This is exactly the line form with m[j] = -2*prefix[j], x[i] = prefix[i], and b[j] = dp[j] + prefix[j]^2. Recognizing this transformation is the key skill for applying convex hull trick dp effectively.

When to Use Convex Hull Trick DP

Use convex hull trick dp when you have three conditions: the DP transition is of the linear form described above, N is too large for O(N^2) (typically N > 5000), and you can efficiently maintain the set of lines. If slopes m[j] are added in monotonic order and query points x[i] are also monotonic, a deque-based O(N) solution is possible. If only one of them is monotonic, you can achieve O(N log N) with a balanced structure. If neither is monotonic, the Li Chao tree provides an O(N log C) solution where C is the coordinate range.

2. How It Works

The mechanism of convex hull trick dp can be understood in two phases: line insertion and query. When we compute dp[j], we create a new line representing state j and insert it into a data structure that maintains the convex hull. When we need to compute dp[i], we query that structure at x = x[i] to find the line giving the minimum value. The efficiency comes from not having to evaluate every line at query time.

Geometrically, each line is infinite. The lower envelope of a set of lines is a piecewise linear convex function. The breakpoints where one line becomes better than another are intersection points. If slopes are sorted, these intersection points are also sorted. This monotonicity allows us to maintain the hull in order and discard lines that will never be optimal. A line l2 is unnecessary if there exists a point where l1 and l3 intersect and both are better than l2 at that point, meaning l2 is completely covered.

The classic redundancy check for three lines l1, l2, l3 added in order of slope uses cross multiplication to avoid floating point errors. For a minimum hull with increasing slopes, l2 is unnecessary if intersection(l1, l2) >= intersection(l2, l3). Equivalently, (b3 - b1)*(m1 - m2) < (b2 - b1)*(m1 - m3). This integer arithmetic check is numerically stable and is the core of the deque implementation. Understanding this condition is essential for implementing the trick without precision bugs.

Monotonic vs. Dynamic Hulls

The simplest and fastest variant is the monotonic convex hull trick. It assumes both slopes and queries are monotonic, typically non-decreasing or non-increasing. In this case, we can use a deque. New lines are added to the back, removing redundant lines from the back. Queries are answered from the front, popping lines that are worse than the next line at the current x. Because each line is added and removed at most once, the total time is O(N). This is common when prefix sums are sorted or when a[i] is given in sorted order.

When monotonicity does not hold, we need a dynamic structure. The Li Chao segment tree is the most versatile solution. It works over a fixed x-coordinate domain [X_MIN, X_MAX] and stores the best line for the midpoint of each segment. Insertion recursively traverses the tree, swapping lines at nodes where the new line is better at the midpoint. Querying walks down the tree to find the best line at a specific x. This gives O(log C) per operation regardless of insertion order, where C is the coordinate range, making it ideal for arbitrary DP recurrences.

Min vs. Max Hulls

The logic for minimization and maximization is symmetric but requires careful sign handling. For a minimum query, we maintain the lower envelope and discard lines that are never the lowest. For a maximum query, we maintain the upper envelope. The redundancy condition flips. Many implementations handle both by negating slopes and intercepts or by flipping comparison operators. A common pitfall is mixing up the inequality direction, which silently produces wrong answers. Always test your implementation on both small brute-force cases for min and max variants.

3. Implementation

Implementing convex hull trick dp correctly requires attention to data types, overflow, and comparison logic. Python's arbitrary-precision integers eliminate overflow concerns, but in languages like C++ you must use 64-bit integers and be wary of (b3 - b1)*(m1 - m2) overflowing 64 bits. The following examples show robust Python implementations for the most common scenarios, with detailed comments and proper handling of edge cases.

The first step in any implementation is to clearly define your line representation and evaluation function. A line is simply a pair (m, b) with an eval(x) method. Keeping this abstraction clean makes the hull logic easier to reason about and test. You should also decide whether you need to handle integer or floating point coordinates, as this affects the Li Chao tree domain.

Below are four production-ready implementations covering the spectrum from naive baseline to fully dynamic. All code escapes comparison operators for HTML safety but is otherwise directly executable in Python 3.

Baseline Naive DP for Verification

# Naive O(N^2) DP - Use as brute force for testing CHT
# dp[i] = min_{j < i} (dp[j] + (a[i] - a[j])**2 + C)
def naive_dp(a, C):
    n = len(a)
    dp = [float('inf')] * n
    dp[0] = 0  # base case
    for i in range(1, n):
        best = float('inf')
        for j in range(i):
            # Transition cost: quadratic distance + constant
            cost = dp[j] + (a[i] - a[j]) * (a[i] - a[j]) + C
            if cost < best:
                best = cost
        dp[i] = best
    return dp

# Example: a = [0, 2, 5, 6], C = 10
# This will be optimized to O(N log N) with CHT below

Monotonic Convex Hull Trick with Deque - O(N)

from collections import deque

class Line:
    def __init__(self, m, b):
        self.m = m  # slope
        self.b = b  # intercept
    def eval(self, x):
        return self.m * x + self.b

def is_bad(l1, l2, l3):
    """
    Returns True if l2 is unnecessary between l1 and l3.
    For minimum hull with increasing slopes.
    Uses cross multiplication to avoid floating point.
    l2 is bad if intersection(l1,l3) <= intersection(l1,l2)
    """
    # (b3 - b1)*(m1 - m2) < (b2 - b1)*(m1 - m3)
    return (l3.b - l1.b) * (l1.m - l2.m) < (l2.b - l1.b) * (l1.m - l3.m)

def monotonic_cht_dp(a, C):
    """
    Solves dp[i] = min_{j < i} (dp[j] + (a[i]-a[j])^2 + C)
    Assumes a is sorted increasingly so slopes m[j] = -2*a[j] are decreasing
    and queries x[i] = a[i] are increasing. Adapt is_bad for order.
    """
    n = len(a)
    dp = [0] * n
    hull = deque()

    # Initial line from j=0: m = -2*a[0], b = dp[0] + a[0]^2
    hull.append(Line(-2 * a[0], dp[0] + a[0] * a[0]))

    for i in range(1, n):
        x = a[i]
        # Query: pop front while next line is better
        while len(hull) >= 2 and hull[0].eval(x) >= hull[1].eval(x):
            hull.popleft()
        best = hull[0].eval(x)
        dp[i] = x * x + best + C

        # Create new line for this i
        new_line = Line(-2 * x, dp[i] + x * x)
        # Maintain hull: remove last line while it becomes redundant
        while len(hull) >= 2 and is_bad(hull[-2], hull[-1], new_line):
            hull.pop()
        hull.append(new_line)
    return dp

Li Chao Segment Tree - O(N log C) for Arbitrary Order

class LiChaoNode:
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.line = None
        self.left = None
        self.right = None

class LiChaoTree:
    def __init__(self, x_min, x_max):
        self.root = LiChaoNode(x_min, x_max)
        self.INF = 10**30

    def _eval(self, line, x):
        if line is None:
            return self.INF
        return line.m * x + line.b

    def add_line(self, new_line, node=None):
        if node is None:
            node = self.root
        l, r = node.l, node.r
        mid = (l + r) // 2

        cur = node.line
        if cur is None:
            node.line = new_line
            return

        # At mid, keep better line in node, push worse down
        if self._eval(new_line, mid) < self._eval(cur, mid):
            node.line, new_line = new_line, cur
            cur = node.line

        if l == r:
            return

        # Decide which side new_line can beat cur
        if self._eval(new_line, l) < self._eval(cur, l):
            if node.left is None:
                node.left = LiChaoNode(l, mid)
            self.add_line(new_line, node.left)
        elif self._eval(new_line, r) < self._eval(cur, r):
            if node.right is None:
                node.right = LiChaoNode(mid + 1, r)
            self.add_line(new_line, node.right)

    def query(self, x, node=None):
        if node is None:
            node = self.root
        res = self._eval(node.line, x)
        if node.l == node.r:
            return res
        mid = (node.l + node.r) // 2
        if x <= mid and node.left is not None:
            return min(res, self.query(x, node.left))
        if x > mid and node.right is not None:
            return min(res, self.query(x, node.right))
        return res

def lichao_dp(a, C, x_min=-10**6, x_max=10**6):
    n = len(a)
    dp = [0] * n
    tree = LiChaoTree(x_min, x_max)
    tree.add_line(Line(-2 * a[0], dp[0] + a[0]*a[0]))
    for i in range(1, n):
        best = tree.query(a[i])
        dp[i] = a[i]*a[i] + best + C
        tree.add_line(Line(-2 * a[i], dp[i] + a[i]*a[i]))
    return dp

Generic Wrapper for Any Linear DP

# Generic convex hull trick dp wrapper
# Solves dp[i] = min_{j < i} (m[j] * x[i] + b[j]) + add[i]
def convex_hull_trick_dp(m_arr, b_arr, x_arr, add_arr, use_lichao=False):
    n = len(x_arr)
    dp = [0] * n
    if use_lichao:
        # Use Li Chao for arbitrary x order
        X_MIN = min(x_arr)
        X_MAX = max(x_arr)
        tree = LiChaoTree(X_MIN, X_MAX)
        tree.add_line(Line(m_arr[0], b_arr[0]))
        for i in range(1, n):
            best = tree.query(x_arr[i])
            dp[i] = best + add_arr[i]
            tree.add_line(Line(m_arr[i], b_arr[i] + dp[i] - b_arr[i]))
        return dp
    else:
        # Monotonic deque - requires m_arr sorted and x_arr sorted
        hull = deque()
        hull.append(Line(m_arr[0], b_arr[0]))
        for i in range(1, n):
            x = x_arr[i]
            while len(hull) >= 2 and hull[0].eval(x) >= hull[1].eval(x):
                hull.popleft()
            dp[i] = hull[0].eval(x) + add_arr[i]
            new_line = Line(m_arr[i], b_arr[i] + dp[i])
            # Note: b_arr here should be base intercept without dp
            while len(hull) >= 2 and is_bad(hull[-2], hull[-1], new_line):
                hull.pop()
            hull.append(new_line)
        return dp

4. Step-by-Step Example

To solidify understanding, let's walk through a concrete convex hull trick dp example end-to-end. Consider the problem: given sorted array a = [0, 1, 4, 6] and constant C = 0, compute dp[i] = min_{j < i} dp[j] + (a[i] - a[j])^2 with dp[0] = 0. The naive solution would evaluate 6 transitions, but CHT will do it with 4 line insertions and 3 queries. We will trace the monotonic deque version.

First, we transform the recurrence. Expanding (a[i] - a[j])^2 = a[i]^2 + a[j]^2 - 2*a[i]*a[j], we get dp[i] = a[i]^2 + min_{j < i} (-2*a[j] * a[i] + dp[j] + a[j]^2). So m[j] = -2*a[j], x[i] = a[i], b[j] = dp[j] + a[j]^2. For our array: m = [0, -2, -8, -12] (decreasing) and x = [0, 1, 4, 6] (increasing). Since slopes are decreasing and queries increasing, we need to adapt the is_bad check for decreasing slopes, or simply reverse the inequality. For this walkthrough we will use the standard increasing-slope logic by negating, but the principle is identical.

Initialize: dp[0]=0. Line0: y = 0*x + 0 (since m0=0, b0=0). Hull = [Line0].

Iteration Details

i=1, x=1: Query hull at x=1. Only Line0 exists, value = 0*1+0=0. So dp[1] = x^2 + best = 1 + 0 = 1. This corresponds to transition from j=0: (1-0)^2=1. Create Line1: m1=-2, b1=dp1 + a1^2 = 1+1=2 => y=-2x+2. Check redundancy: hull has 1 line, no removal. Hull = [Line0, Line1]. Intersection of Line0 and Line1 is at x=1. For x < 1, Line0 is better; for x > 1, Line1 is better.

i=2, x=4: Query at x=4. Evaluate hull front: Line0(4)=0, Line1(4)=-8+2=-6. Since Line1 is better, pop Line0. Best = -6. dp[2]=16 + (-6)=10. Let's verify via brute force: j=0 => 0+16=16, j=1 => 1+(3)^2=10, so min is 10 correct. Create Line2: m2=-8, b2=10+16=26 => y=-8x+26. Check if Line1 is bad between Line0 and Line2: intersection(Line0,Line1)=1, intersection(Line1,Line2)=4. Since 1 < 4, Line1 is still useful, keep it. Hull = [Line1, Line2] (Line0 was popped at query time, but logically hull is [Line1, Line2]).

i=3, x=6: Query at x=6. Line1(6)=-12+2=-10, Line2(6)=-48+26=-22. Line2 is better, so pop Line1. Best=-22. dp[3]=36-22=14. Brute force: j0:36, j1:1+25=26, j2:10+4=14 => 14 correct. Create Line3: m3=-12, b3=14+36=50 => y=-12x+50. Check redundancy: intersection(Line1,Line2)=4, intersection(Line2,Line3)=6, so Line2 remains useful. Final hull = [Line2, Line3]. The DP array is [0,1,10,14].

Visualizing the Hull

If we plotted these four lines, the lower envelope would be: Line0 from x=-inf to 1, Line1 from 1 to 4, Line2 from 4 to 6, Line3 beyond 6. Each line dominates a contiguous interval, and intervals appear in order of slope. The deque precisely maintains this ordered envelope. Notice how Line0 was discarded after x=1 because it never becomes optimal again due to monotonic queries. This is why the deque query can pop from the front permanently.

This example also highlights why sorting matters. If a were unsorted, say [0,6,1,4], the queries would not be monotonic and the deque's front-popping would be invalid. You would need Li Chao, which would still give correct answers but with O(log C) overhead. Always verify monotonicity of both slopes and query points before choosing the deque optimization.

5. Complexity Analysis

The primary motivation for convex hull trick dp is complexity reduction. The naive DP evaluates all previous states for each i, leading to quadratic time that fails for large N. CHT reduces this by maintaining a geometric structure that answers each DP transition in logarithmic or constant amortized time. Understanding the precise tradeoffs helps you choose the right variant for constraints.

Space usage is also dramatically improved in terms of constant factors, though asymptotically both naive and optimized versions use O(N) for the DP array. The hull itself stores at most N lines, but in practice often far fewer because many lines become redundant quickly. For random data, the expected hull size is O(log N), though worst-case remains O(N).

The following table summarizes the time and space complexity for the major convex hull trick dp variants. Best case assumes favorable data distribution, average case assumes random inputs, and worst case is the theoretical upper bound.

* Static Li Chao with array implementation uses O(C) space where C is coordinate range; dynamic node allocation uses O(N log C) in worst case but typically much less.

Amortized Analysis of Deque Variant

The O(N) bound for the monotonic deque is amortized. Each line is inserted once and removed at most once from the back (during insertion) and at most once from the front (during query). Therefore the total number of deque operations across the entire DP is O(N). No single query is guaranteed O(1) worst-case if many lines are popped, but the aggregate is linear. This is analogous to the analysis of a queue with monotone stack.

For Li Chao, each insertion traverses O(log C) nodes and each query traverses O(log C) nodes, giving strict O(log C) per operation, not amortized. C is typically up to 1e9, so log C is about 30, which is effectively constant for N up to 1e6. The constant factor is higher than deque due to recursion and node allocation, but it remains highly efficient.

Space Considerations

All variants need O(N) for the dp array itself. The hull adds O(N) in the worst case. Li Chao with dynamic nodes allocates at most O(log C) new nodes per insertion, but many insertions share nodes, so actual memory is often O(N) in practice for random slopes. If memory is tight and C is small (e.g., x in [0, 1e5]), a static array-based Li Chao using 4*C nodes may be more cache-friendly and simpler, though it uses O(C) space regardless of N.

6. Variations and Optimizations

Beyond the basic deque and Li Chao implementations, several variations and optimizations extend the reach of convex hull trick dp to broader problem classes. Choosing the right variation depends on the monotonicity properties of your DP and whether you need to handle online queries, persistent versions, or integer overflow.

One important optimization is the use of integer cross multiplication versus floating point intersection. Floating point introduces precision errors when slopes and intercepts are large (up to 1e18), causing incorrect removal of lines. The cross product method using (b3 - b1)*(m1 - m2) < (b2 - b1)*(m1 - m3) is exact for integers but can overflow 64-bit. In Python this is safe, but in C++ you need __int128. An alternative is to use fractions with careful gcd handling, but cross multiplication is standard.

Another common optimization is to avoid Li Chao entirely when only one dimension is monotonic. If slopes are monotonic but queries are arbitrary, you can maintain the hull in a vector sorted by intersection point and binary search for the best line at query time, achieving O(N log N). Similarly, if queries are monotonic but slopes are arbitrary, you can use a balanced BST keyed by slope. These hybrids are simpler than Li Chao and have lower constant factors.

Divide and Conquer Optimization vs. CHT

Divide and conquer optimization is often confused with convex hull trick dp because both optimize DP. However, D&C optimization applies when the opt array is monotonic: opt[i] <= opt[i+1], where opt[i] is the best j for dp[i]. CHT applies when the transition is linear. Some problems satisfy both, allowing either technique, but they are distinct. D&C optimization yields O(N log N) and is easier to implement if you can prove monotonicity of opt, while CHT is more general for linear recurrences.

Knuth and Other DP Optimizations

Knuth optimization requires quadrangle inequality and monotonicity, giving O(N^2) -> O(N^2) with smaller constant or O(N^2) -> O(N log N) in some cases, but it does not apply to the linear form. The convex hull trick is specifically for linear recurrences. Understanding which optimization applies is a key interview skill. If you see dp[i][j] = min_{k < j} dp[i-1][k] + C[k][j] with quadrangle inequality, think Knuth or D&C. If you see m[j]*x[i], think CHT.

Persistent and Offline Variants

For problems requiring rollback or persistent DP states, a persistent Li Chao tree can be built using path copying, where each insertion creates O(log C) new nodes without mutating old versions. This allows querying historical hulls, useful for DP on trees or divide-and-conquer DP. Offline techniques like sorting queries by x and processing lines in slope order can also achieve O((N+Q) log N) without a dynamic structure, which is useful when all queries are known upfront.

7. Real-World Applications

While convex hull trick dp is most famous in competitive programming, its underlying principle—optimizing linear DP transitions via geometric envelopes—appears in many real-world systems where large-scale dynamic programming is used for resource allocation, scheduling, and optimization. The technique is not limited to abstract arrays; it models any problem where cost is a linear function of a decision variable.

In web servers and load balancing, consider scheduling batch jobs with convex cost functions. Suppose you must partition N requests into batches where the cost of a batch from j+1 to i is (load[i] - load[j])^2 + overhead. The DP to minimize total cost is exactly the CHT form. With N=1e6 requests per minute, O(N^2) is impossible, but O(N) CHT allows real-time optimal batching, reducing latency and server costs.

In databases, query optimization and join ordering can involve DP over subsets with linear cost models. While not always strictly CHT, the idea of maintaining a lower envelope of cost functions is used in parametric query optimization where the optimal plan depends linearly on selectivity estimates. The hull represents the set of Pareto-optimal plans.

Networking and Infrastructure

In networking, convex hull trick dp is used for traffic engineering and resource provisioning. For example, laying fiber optic cables or provisioning bandwidth where cost is convex in distance or capacity. The DP for placing k facilities to minimize sum of squared distances to clients can be optimized with CHT, as the cost function is quadratic. Similarly, video streaming with adaptive bitrate uses DP to choose quality levels where switching cost is linear in bandwidth, and CHT speeds up the per-frame decision.

Another application is in computational geometry and finance. The classic "convex hull trick" name comes from geometry, but the same structure is used in financial portfolio optimization where transaction costs are linear and you need to compute optimal trading trajectories over time. The DP for optimal execution with market impact often has the form dp[t] = min_{s < t} dp[s] + alpha*(x[t]-x[s])^2 + beta*x[t], which is CHT-optimizable.

Summary of Use Cases

Even when the problem does not exactly match the textbook form, the insight of maintaining a lower envelope of lines is broadly applicable. Any system that repeatedly queries the minimum of many linear functions benefits from these structures, which is why Li Chao trees are now standard in many high-performance libraries.

8. Comparison with Alternatives

Choosing the right DP optimization is critical. Convex hull trick dp is powerful but not universal. It requires a linear transition; if your DP does not have that form, other optimizations like divide and conquer or Knuth may be more appropriate. This section compares CHT with its closest alternatives to help you decide quickly during contests or system design.

The key differentiator is the condition each optimization requires. CHT needs linearity, divide and conquer needs monotonicity of the argmin (monge property), and Knuth needs quadrangle inequality plus monotonicity. Some problems satisfy multiple conditions, giving you a choice. In those cases, implementation simplicity and constant factors should guide you. Monotonic CHT is the simplest and fastest when applicable; Li Chao is the most general but has higher overhead.

Another alternative is to use a generic convex optimization library or to brute force with pruning if N is moderate (N < 5000). For N up to 1e5, O(N log N) is usually required, and CHT delivers that. For N up to 1e6, only O(N) monotonic CHT may pass within time limits in Python, requiring PyPy and careful micro-optimizations or switching to C++.

When to Prefer Each Approach

Prefer monotonic CHT when you can prove slopes and queries are sorted. This is common with prefix sums of non-negative arrays. It is the fastest and simplest. Prefer Li Chao when you cannot guarantee order, or when lines are added and queried interleaved arbitrarily. Prefer divide and conquer when your cost function satisfies monge but is not linear, such as cost(j,i) = w[j][i] with quadrangle inequality. Prefer Knuth for problems like optimal binary search tree where the DP is 2D and quadrangle holds.

In practice, many competitive programmers default to Li Chao because it is general and hard to get wrong once implemented correctly, even if it is slightly slower than deque. Having a well-tested Li Chao template in your library is invaluable. For production systems, the choice may depend on latency requirements: deque has better cache locality and lower constant factors, making it preferable for real-time batch scheduling.

9. Common Mistakes and Best Practices

Even experienced developers make subtle errors when implementing convex hull trick dp. The technique is notorious for off-by-one errors, integer overflow, and incorrect handling of equal slopes. This section catalogs the most frequent pitfalls and provides best practices to avoid them, ensuring your implementation is both correct and maintainable.

One of the most common mistakes is not handling equal slopes correctly. If two lines have the same slope m, only the one with smaller intercept b (for min query) can ever be optimal. The other is strictly dominated. Failing to discard the worse line before insertion leads to division by zero in intersection calculations and breaks the is_bad logic, which assumes distinct slopes. Always check for equal slopes at insertion time and keep only the best.

Another frequent error is using floating point to compute intersections. With slopes and intercepts up to 1e9, the intersection x-coordinate can be a fraction that loses precision in double, causing incorrect ordering of lines. The integer cross multiplication method is exact and should always be preferred. In Python, integers are arbitrary precision, so overflow is not an issue, but in C++ you must cast to __int128 for the product.

Pitfalls in Monotonicity Assumptions

Assuming monotonicity when it does not hold is a silent killer. For example, if a[i] is not sorted, the slopes -2*a[j] will not be monotonic, and the deque's front-popping logic fails. The DP will still run but produce wrong answers that are hard to debug because small test cases may still pass. Always explicitly verify that your input guarantees sorted order or sort it yourself if the problem allows. If sorting changes the DP semantics, you must use Li Chao.

Similarly, mixing up min vs. max hull logic is common. The is_bad condition flips depending on whether you maintain upper or lower envelope and whether slopes are increasing or decreasing. A robust practice is to write a single is_bad that is parameterized or to always transform a max query into a min query by negating slopes and intercepts, then reuse the min hull code. Unit test both variants.

Best Practices Checklist

• Brute force validator: Always implement a naive O(N^2) DP for N <= 200 and compare against CHT on random small tests with a stress tester. Run thousands of random cases.
• Handle equal slopes: At insertion, if m_new == m_last, keep only the line with smaller b (for min) and discard the other.
• Use integer arithmetic: Never use (b3-b1)/(m1-m3) floating division. Use cross multiplication (b3-b1)*(m1-m2) < (b2-b1)*(m1-m3).
• Test edge cases: N=1, N=2, all equal a[i], negative slopes, large values near 1e18, and both increasing and decreasing query orders.
• Choose the right structure: If slopes and queries are monotonic, use deque for O(N). Otherwise use Li Chao. Do not force deque when Li Chao is needed.
• Encapsulate lines: Use a Line class with eval method for clarity and to avoid repeating m*x+b logic.
• Coordinate compression for Li Chao: If x range is huge (1e18), compress queries to sorted unique values and build Li Chao over indices to reduce log factor and memory.
• Document invariants: Comment whether your hull assumes increasing or decreasing slopes and whether queries are increasing. This prevents future misuse.

Finally, consider performance in Python. Loops with heavy Python overhead can be slow for N=2e5. Use PyPy, local variable binding, and avoid recursion depth issues in Li Chao by implementing iterative versions if needed. For extreme constraints, consider using Numba or switching to C++ for the hull operations while keeping DP logic in Python.

10. Interview Questions

Convex hull trick dp is a favorite topic for advanced algorithm interviews at top tech companies and for competitive programming contests. Interviewers use it to test your ability to recognize optimization opportunities, transform recurrences, and reason about geometric data structures. Below are common interview questions with guidance on how to approach them.

Question 1: Recognize the CHT Form

Given DP: dp[i] = min_{j < i} (dp[j] + a[j]*b[i] + c[j]), where a, b, c are arrays. How would you optimize it? What is the time complexity before and after?

Answer approach: Identify that this is dp[i] = min_{j < i} (m[j]*x[i] + b[j]) + C with m[j]=a[j], x[i]=b[i