数据结构优化DP

概述

数据结构优化动态规划是一种通过高级数据结构将低效DP解决方案转换为最优解决方案的强大技术。这种技术包括线段树DP优化、凸包优化（CHT）、分治优化和李超线段树。这些方法可以将时间复杂度从O(n²)或O(n³)降低到O(n log n)甚至O(n)，使得在竞赛编程时间限制内解决以前难以处理的问题成为可能。

线段树DP优化

核心概念

当DP转移涉及区间查询（最小值、最大值、求和）时，线段树可以将这些操作从每次查询O(n)优化到O(log n)。典型的模式是：dp[i] = optimal(dp[j] + cost(j, i))，其中j在某个区间内变化。

带懒标记的线段树DP

#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);
    }
};

// 示例：将数组分成k段的最小代价
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++) {
                // 从有效的前面位置查询最小值
        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; // 最大段长度

    
    cout << "数组: ";
    for (int x : arr) cout << x << " ";
    cout << "\n最大段长度: " << k << endl;
    
    vector<long long> dp = minCostSplit(arr, k);
    cout << "最小代价: " << dp.back() << endl;
    
    return 0;
}

带懒标记的线段树支持高效的区间更新和查询，对于需要同时更新多个位置的复杂DP优化是必不可少的。

凸包优化（CHT）

何时使用CHT

CHT优化形如dp[i] = min(dp[j] + b[j] * a[i] + c[i])的DP转移，其中斜率b[j]单调且查询点a[i]单调。这将复杂度从O(n²)降低到O(n)。

双端队列优化的凸包技巧

#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;
    }
    
        // 检查在给定两条其他直线的情况下，这条直线是否冗余
    bool isBad(const Line& l1, const Line& l2) const {
                // 叉积比较以避免浮点数
        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);
        
                // 移除变得冗余的直线
        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};
        
                // 移除不再最优的直线
        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;
    }
};

// 示例：工厂生产优化
// 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); // 初始状态

    
    for (int i = 1; i <= n; i++) {
        auto [cost, from] = cht.query(demand[i - 1]);
        dp[i] = cost + production_cost[i - 1];
        
                // 为未来转移添加新直线
        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 << "设置成本: ";
    for (long long x : setup_cost) cout << x << " ";
    cout << "\n需求: ";
    for (long long x : demand) cout << x << " ";
    cout << "\n生产成本: ";
    for (long long x : production_cost) cout << x << " ";
    cout << endl;
    
    vector<long long> dp = optimizeProduction(setup_cost, demand, production_cost);
    cout << "最小总成本: " << dp.back() << endl;
    
    return 0;
}

CHT维护线性函数的凸包，当查询和斜率都是单调的时候，允许在摊销O(1)时间内进行最优DP转移。

李超线段树

高级直线管理

李超线段树在CHT条件不满足时处理动态直线插入和点查询。它为每个段维护最优直线，支持任意直线插入顺序。

李超线段树实现

#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);
    }
};

// 示例：任意直线插入的动态规划
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); // 初始直线

    
    for (int i = 1; i <= n; i++) {
        dp[i] = lct.queryMin(multipliers[i - 1]) + costs[i - 1];
        
                // 为未来状态添加新直线
        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 << "成本: ";
    for (int x : costs) cout << x << " ";
    cout << "\n乘数: ";
    for (int x : multipliers) cout << x << " ";
    cout << endl;
    
    vector<long long> dp = solveWithLiChao(costs, multipliers);
    cout << "最优结果: " << dp.back() << endl;
    
    return 0;
}

李超线段树为每个段维护最优直线，处理CHT无法管理的任意直线插入模式。

分治DP

四边形不等式优化

当DP递推满足四边形不等式（Monge性质）时，分治优化将复杂度从O(kn²)降低到O(kn log n)。关键洞察是最优分割点是单调的。

分治DP优化

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

class DivideConquerDP {
private:
    vector<vector<long long>> dp;
    vector<long long> cost;
    int n, k;
    
        // 代价函数 - 必须满足四边形不等式
    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;
        
                // 为位置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;
        
                // 递归解决左右两部分
        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;
        
                // 计算前缀和用于代价函数
        for (int i = 1; i < n; i++) {
            cost[i] += cost[i - 1];
        }
        
        dp.assign(k + 1, vector<long long>(n, LLONG_MAX));
        
                // 基础情况：一组
        for (int i = 0; i < n; i++) {
            dp[1][i] = C(0, i);
        }
        
                // 使用分治填充DP表
        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; // 组数

    
    cout << "数组: ";
    for (long long x : arr) cout << x << " ";
    cout << "\n组数: " << k << endl;
    
    DivideConquerDP solver;
    vector<long long> result = solver.solve(arr, k);
    
    cout << "最小代价: " << result[arr.size() - 1] << endl;
    
    return 0;
}

分治DP利用代价函数满足四边形不等式时最优分割点的单调性，显著降低时间复杂度。

优化策略指南

🎯 何时使用每种技术

线段树： DP转移中的区间查询
CHT: 斜率单调的线性函数
李超： 任意直线插入模式
分治： 满足四边形不等式

⚡ 性能考虑

内存： 线段树需要4n空间
常数： CHT比李超有更好的常数
精度： 尽可能使用整数运算
缓存： 顺序访问模式更快

🔧 实现技巧

溢出： 中间计算使用long long
边界情况： 处理空区间和单元素
调试： 验证单调性条件
测试： 小输入与暴力比较

📊 复杂度分析

线段树DP： 每次转移O(n log n)
CHT: 单调查询总计O(n)
李超： n条直线和查询O(n log n)
分治DP： k组O(kn log n)