Data Structure Optimized DP

Overview

Data Structure Optimized Dynamic Programming is a powerful technique that transforms inefficient DP solutions into optimal ones using advanced data structures. This technique includes segment tree DP optimization, Convex Hull Trick (CHT), divide and conquer optimization, and Li Chao segment tree. These methods can reduce time complexity from O(n²) or O(n³) to O(n log n) or even O(n), making previously intractable problems solvable within competitive programming time limits.

Segment Tree DP Optimization

Core Concept

When DP transitions involve range queries (min, max, sum), segment trees can optimize these operations from O(n) to O(log n) per query. The typical pattern is: dp[i] = optimal(dp[j] + cost(j, i)) where j ranges over some interval.

Segment Tree DP with Lazy Propagation

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class SegmentTreeDP {
private:
    vector<long long> tree, lazy;
    int n;
    
    void push(int node, int start, int end) {
        if (lazy[node] != 0) {
            tree[node] += lazy[node];
            if (start != end) {
                lazy[2 * node] += lazy[node];
                lazy[2 * node + 1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }
    
    void updateRange(int node, int start, int end, int l, int r, long long val) {
        push(node, start, end);
        if (start > r || end < l) return;
        
        if (start >= l && end <= r) {
            lazy[node] += val;
            push(node, start, end);
            return;
        }
        
        int mid = (start + end) / 2;
        updateRange(2 * node, start, mid, l, r, val);
        updateRange(2 * node + 1, mid + 1, end, l, r, val);
        
        push(2 * node, start, mid);
        push(2 * node + 1, mid + 1, end);
        tree[node] = min(tree[2 * node], tree[2 * node + 1]);
    }
    
    long long queryRange(int node, int start, int end, int l, int r) {
        if (start > r || end < l) return LLONG_MAX;
        
        push(node, start, end);
        if (start >= l && end <= r) return tree[node];
        
        int mid = (start + end) / 2;
        return min(queryRange(2 * node, start, mid, l, r),
                  queryRange(2 * node + 1, mid + 1, end, l, r));
    }
    
public:
    SegmentTreeDP(int size) : n(size) {
        tree.assign(4 * n, LLONG_MAX);
        lazy.assign(4 * n, 0);
    }
    
    void update(int l, int r, long long val) {
        updateRange(1, 0, n - 1, l, r, val);
    }
    
    long long query(int l, int r) {
        if (l > r) return LLONG_MAX;
        return queryRange(1, 0, n - 1, l, r);
    }
    
    void pointUpdate(int idx, long long val) {
        updateRange(1, 0, n - 1, idx, idx, val);
    }
};

// Example: Minimum cost to split array into k segments
vector<long long> minCostSplit(vector<int>& arr, int k) {
    int n = arr.size();
    vector<long long> dp(n + 1, LLONG_MAX);
    dp[0] = 0;
    
    SegmentTreeDP segTree(n + 1);
    segTree.pointUpdate(0, 0);
    
    for (int i = 1; i <= n; i++) {
                // Query minimum from valid previous positions
        long long minPrev = segTree.query(max(0, i - k), i - 1);
        if (minPrev != LLONG_MAX) {
            dp[i] = minPrev + arr[i - 1];
            segTree.pointUpdate(i, dp[i]);
        }
    }
    
    return dp;
}

int main() {
    vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
    int k = 3; // Maximum segment length

    
    cout << "Array: ";
    for (int x : arr) cout << x << " ";
    cout << "\nMax segment length: " << k << endl;
    
    vector<long long> dp = minCostSplit(arr, k);
    cout << "Minimum cost: " << dp.back() << endl;
    
    return 0;
}

Segment trees with lazy propagation support efficient range updates and queries, essential for complex DP optimizations where multiple positions need simultaneous updates.

Convex Hull Trick (CHT)

When to Use CHT

CHT optimizes DP transitions of the form: dp[i] = min(dp[j] + b[j] * a[i] + c[i]) where slopes b[j] are monotonic and query points a[i] are monotonic. This reduces complexity from O(n²) to O(n).

Convex Hull Trick with Deque Optimization

#include <iostream>
#include <vector>
#include <deque>
#include <climits>
using namespace std;

struct Line {
    long long slope, intercept;
    int id;
    
    Line(long long slope, long long intercept, int id = -1) 
        : slope(slope), intercept(intercept), id(id) {}
    
    long long eval(long long x) const {
        return slope * x + intercept;
    }
    
        // Check if this line is redundant given two other lines
    bool isBad(const Line& l1, const Line& l2) const {
                // Cross product comparison to avoid floating point
        return (intercept - l1.intercept) * (l1.slope - l2.slope) 
               <= (l2.intercept - l1.intercept) * (l1.slope - slope);
    }
};

class ConvexHullTrick {
private:
    deque<Line> lines;
    
public:
    void addLine(long long slope, long long intercept, int id = -1) {
        Line newLine(slope, intercept, id);
        
                // Remove lines that become redundant
        while (lines.size() >= 2 && 
               newLine.isBad(lines[lines.size()-2], lines[lines.size()-1])) {
            lines.pop_back();
        }
        
        lines.push_back(newLine);
    }
    
    pair<long long, int> query(long long x) {
        if (lines.empty()) return {LLONG_MAX, -1};
        
                // Remove lines that are no longer optimal
        while (lines.size() >= 2 && 
               lines[0].eval(x) >= lines[1].eval(x)) {
            lines.pop_front();
        }
        
        return {lines[0].eval(x), lines[0].id};
    }
    
    long long queryValue(long long x) {
        return query(x).first;
    }
};

// Example: Factory production optimization
// dp[i] = min(dp[j] + setup_cost[j] * demand[i] + production_cost[i])
vector<long long> optimizeProduction(vector<long long>& setup_cost, 
                                    vector<long long>& demand, 
                                    vector<long long>& production_cost) {
    int n = setup_cost.size();
    vector<long long> dp(n + 1, LLONG_MAX);
    dp[0] = 0;
    
    ConvexHullTrick cht;
    cht.addLine(0, 0, 0); // Initial state

    
    for (int i = 1; i <= n; i++) {
        auto [cost, from] = cht.query(demand[i - 1]);
        dp[i] = cost + production_cost[i - 1];
        
                // Add new line for future transitions
        if (i < n) {
            cht.addLine(-setup_cost[i - 1], dp[i], i);
        }
    }
    
    return dp;
}

int main() {
    vector<long long> setup_cost = {2, 3, 1, 4, 2};
    vector<long long> demand = {1, 2, 3, 2, 1};
    vector<long long> production_cost = {5, 3, 4, 2, 6};
    
    cout << "Setup costs: ";
    for (long long x : setup_cost) cout << x << " ";
    cout << "\nDemand: ";
    for (long long x : demand) cout << x << " ";
    cout << "\nProduction costs: ";
    for (long long x : production_cost) cout << x << " ";
    cout << endl;
    
    vector<long long> dp = optimizeProduction(setup_cost, demand, production_cost);
    cout << "Minimum total cost: " << dp.back() << endl;
    
    return 0;
}

CHT maintains a convex hull of linear functions, allowing optimal DP transitions in O(1) amortized time when queries and slopes are monotonic.

Li Chao Segment Tree

Advanced Line Management

Li Chao segment tree handles dynamic line insertion and point queries when CHT conditions aren't met. It maintains the optimal line for each segment, supporting arbitrary line insertion order.

Li Chao Segment Tree Implementation

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct Line {
    long long a, b; // y = ax + b
    
    Line(long long a = 0, long long b = LLONG_MAX) : a(a), b(b) {}
    
    long long eval(long long x) const {
        if (b == LLONG_MAX) return LLONG_MAX;
        return a * x + b;
    }
};

class LiChaoTree {
private:
    vector<Line> tree;
    int n;
    
    void update(int node, int start, int end, Line line) {
        if (start == end) {
            if (line.eval(start) < tree[node].eval(start)) {
                tree[node] = line;
            }
            return;
        }
        
        int mid = (start + end) / 2;
        bool left_better = line.eval(start) < tree[node].eval(start);
        bool mid_better = line.eval(mid) < tree[node].eval(mid);
        
        if (mid_better) {
            swap(tree[node], line);
        }
        
        if (left_better != mid_better) {
            update(2 * node, start, mid, line);
        } else {
            update(2 * node + 1, mid + 1, end, line);
        }
    }
    
    long long query(int node, int start, int end, int pos) {
        if (start == end) {
            return tree[node].eval(pos);
        }
        
        int mid = (start + end) / 2;
        long long result = tree[node].eval(pos);
        
        if (pos <= mid) {
            result = min(result, query(2 * node, start, mid, pos));
        } else {
            result = min(result, query(2 * node + 1, mid + 1, end, pos));
        }
        
        return result;
    }
    
public:
    LiChaoTree(int size) : n(size) {
        tree.assign(4 * n, Line());
    }
    
    void addLine(long long a, long long b) {
        update(1, 0, n - 1, Line(a, b));
    }
    
    long long queryMin(int x) {
        return query(1, 0, n - 1, x);
    }
};

// Example: Dynamic programming with arbitrary line insertion
vector<long long> solveWithLiChao(vector<int>& costs, vector<int>& multipliers) {
    int n = costs.size();
    vector<long long> dp(n + 1, LLONG_MAX);
    dp[0] = 0;
    
    LiChaoTree lct(n + 1);
    lct.addLine(0, 0); // Initial line

    
    for (int i = 1; i <= n; i++) {
        dp[i] = lct.queryMin(multipliers[i - 1]) + costs[i - 1];
        
                // Add new line for future states
        lct.addLine(-i, dp[i]);
    }
    
    return dp;
}

int main() {
    vector<int> costs = {3, 1, 4, 1, 5};
    vector<int> multipliers = {2, 1, 3, 2, 1};
    
    cout << "Costs: ";
    for (int x : costs) cout << x << " ";
    cout << "\nMultipliers: ";
    for (int x : multipliers) cout << x << " ";
    cout << endl;
    
    vector<long long> dp = solveWithLiChao(costs, multipliers);
    cout << "Optimal result: " << dp.back() << endl;
    
    return 0;
}

Li Chao segment tree maintains the optimal line for each segment, handling arbitrary line insertion patterns that CHT cannot manage.

Divide and Conquer DP

Quadrangle Inequality Optimization

When the DP recurrence satisfies the quadrangle inequality (Monge property), divide and conquer optimization reduces complexity from O(kn²) to O(kn log n). The key insight is that optimal split points are monotonic.

Divide and Conquer DP Optimization

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

class DivideConquerDP {
private:
    vector<vector<long long>> dp;
    vector<long long> cost;
    int n, k;
    
        // Cost function - must satisfy quadrangle inequality
    long long C(int i, int j) {
        if (i > j) return LLONG_MAX;
        return (cost[j] - cost[i]) * (cost[j] - cost[i]);
    }
    
    void compute(int level, int left, int right, int opt_left, int opt_right) {
        if (left > right) return;
        
        int mid = (left + right) / 2;
        int best_k = -1;
        long long best_cost = LLONG_MAX;
        
                // Find optimal split point for position mid
        for (int split = opt_left; split <= min(mid - 1, opt_right); split++) {
            long long current_cost = dp[level - 1][split] + C(split + 1, mid);
            if (current_cost < best_cost) {
                best_cost = current_cost;
                best_k = split;
            }
        }
        
        dp[level][mid] = best_cost;
        
                // Recursively solve left and right parts
        compute(level, left, mid - 1, opt_left, best_k);
        compute(level, mid + 1, right, best_k, opt_right);
    }
    
public:
    vector<long long> solve(vector<long long>& arr, int groups) {
        n = arr.size();
        k = groups;
        cost = arr;
        
                // Compute prefix sums for cost function
        for (int i = 1; i < n; i++) {
            cost[i] += cost[i - 1];
        }
        
        dp.assign(k + 1, vector<long long>(n, LLONG_MAX));
        
                // Base case: one group
        for (int i = 0; i < n; i++) {
            dp[1][i] = C(0, i);
        }
        
                // Fill DP table using divide and conquer
        for (int level = 2; level <= k; level++) {
            compute(level, level - 1, n - 1, level - 2, n - 2);
        }
        
        return dp[k];
    }
};

int main() {
    vector<long long> arr = {1, 2, 3, 4, 5, 6, 7, 8};
    int k = 3; // Number of groups

    
    cout << "Array: ";
    for (long long x : arr) cout << x << " ";
    cout << "\nNumber of groups: " << k << endl;
    
    DivideConquerDP solver;
    vector<long long> result = solver.solve(arr, k);
    
    cout << "Minimum cost: " << result[arr.size() - 1] << endl;
    
    return 0;
}

Divide and conquer DP leverages the monotonicity of optimal split points when the cost function satisfies quadrangle inequality, dramatically reducing time complexity.

Optimization Strategy Guide

🎯 When to Use Each Technique

Segment Tree: Range queries in DP transitions
CHT: Linear functions with monotonic slopes
Li Chao: Arbitrary line insertion patterns
Divide & Conquer: Quadrangle inequality satisfied

⚡ Performance Considerations

Memory: Segment trees need 4n space
Constants: CHT has better constants than Li Chao
Precision: Use integer arithmetic when possible
Cache: Sequential access patterns are faster

🔧 Implementation Tips

Overflow: Use long long for intermediate calculations
Edge Cases: Handle empty ranges and single elements
Debugging: Verify monotonicity conditions
Testing: Compare with brute force on small inputs

📊 Complexity Analysis

Segment Tree DP: O(n log n) per transition
CHT: O(n) total with monotonic queries
Li Chao: O(n log n) for n lines and queries
D&C DP: O(kn log n) for k groups