1. 引言动态规划DP是算法竞赛和工程面试中的常客但当状态转移需要在一段区间内取最值时朴素做法往往需要 O(n) 的扫描导致整体复杂度上升到 O(n²) 甚至更高。线段树作为一种支持区间查询和单点修改的数据结构恰好可以用来优化这类转移把单次转移的代价降到 O(log n)。本文从原理出发结合典型例题讲解如何用线段树优化 DP。2. 适用场景并不是所有 DP 都需要线段树优化。通常当状态转移方程满足以下特征时可以考虑引入线段树区间最值查询转移时需要从某个下标区间内取最大值或最小值例如 dp[i] max(dp[j]) w(i)其中 j 属于某个连续区间。单点更新每计算完一个 dp[i]需要把它插入到线段树的对应位置供后续状态查询。值域较大如果值域较小可以用树状数组或单调队列当值域较大且需要离散化时线段树依然适用。相比之下如果区间是固定长度的滑动窗口单调队列往往更优如果只涉及前缀最值树状数组或前缀数组就足够了。线段树的优势在于区间端点可以随状态动态变化不受窗口长度限制。3. 核心思想线段树优化 DP 的核心思路可以概括为三步建树用线段树维护 dp 数组的区间最值或区间和、区间乘积等初始时把所有位置设为负无穷求最大值时或正无穷求最小值时。查询计算 dp[i] 时根据转移方程确定需要查询的区间 [L, R]调用线段树的区间查询接口在 O(log n) 时间内得到该区间的最值。更新得到 dp[i] 后把它更新到线段树的第 i 个位置供后续状态查询使用。这样原本 O(n) 的转移被压缩为 O(log n)整体复杂度从 O(n²) 降为 O(n log n)。4. 经典例题最长上升子序列LIS先从一个最简单的例子入手。求一个长度为 n 的数组 a 的最长上升子序列长度。朴素 DP 的状态转移为dp[i] 1 max(dp[j])其中 j i 且 a[j] a[i]这里需要查询的是所有值小于 a[i] 的位置中 dp 的最大值。我们可以用线段树以 a[i] 的值为下标来维护 dp 最大值每次查询区间 [1, a[i] - 1] 的最大值再把 dp[i] 更新到位置 a[i]。如果 a[i] 的值域很大先做离散化即可。下面给出 C 参考实现#include bits/stdc.h using namespace std; const int MAXN 100005; int a[MAXN], dp[MAXN]; int tree[MAXN 2]; void update(int node, int l, int r, int pos, int val) { if (l r) { tree[node] max(tree[node], val); return; } int mid (l r) 1; if (pos mid) update(node 1, l, mid, pos, val); else update(node 1 | 1, mid 1, r, pos, val); tree[node] max(tree[node 1], tree[node 1 | 1]); } int query(int node, int l, int r, int ql, int qr) { if (ql l r qr) return tree[node]; int mid (l r) 1; int res 0; if (ql mid) res max(res, query(node 1, l, mid, ql, qr)); if (qr mid) res max(res, query(node 1 | 1, mid 1, r, ql, qr)); return res; } int main() { int n; cin n; vectorint vals; for (int i 1; i n; i) { cin a[i]; vals.push_back(a[i]); } // 离散化 sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); int ans 0; for (int i 1; i n; i) { int idx lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() 1; int best query(1, 1, n, 1, idx - 1); dp[i] best 1; update(1, 1, n, idx, dp[i]); ans max(ans, dp[i]); } cout ans endl; return 0; }这段代码中线段树的下标是离散化后的值域维护的是对应值域上 dp 的最大值。每次查询 [1, idx - 1] 得到所有小于 a[i] 的值的最大 dp加一即为 dp[i]。5. 进阶例题区间调度类 DP再看一个更典型的区间调度问题。有 n 个任务每个任务有一个开始时间、结束时间和收益任务之间不能重叠求能获得的最大总收益。朴素做法是按结束时间排序后对每个任务向前扫描所有结束时间小于当前开始时间的任务复杂度 O(n²)。用线段树优化后可以按结束时间排序以结束时间为下标建立线段树维护到某个结束时间为止的最大收益。转移方程为dp[i] max(dp[i - 1], query(1, start[i] - 1) profit[i])其中 query(1, start[i] - 1) 表示所有结束时间小于 start[i] 的任务能获得的最大收益。计算完 dp[i] 后把 dp[i] 更新到线段树的 end[i] 位置。这样每个任务只需一次查询和一次更新整体复杂度 O(n log n)。6. 常见陷阱与注意事项离散化边界当值域很大时离散化后要注意查询区间的边界。例如 LIS 中查询 [1, idx - 1]如果 idx 为 1则查询区间为空需要特判返回 0。初始化求最大值时线段树初始值应设为负无穷或 0具体取决于 dp 的语义。如果 dp 允许为 0初始化为 0 即可如果可能出现负数应初始化为负无穷。更新时机一定要先查询再更新避免当前状态被自己影响。如果先更新再查询可能会把 dp[i] 自身算进转移里导致错误。空间大小线段树数组通常开 4 倍节点数即 4 * n防止越界。与单调队列的取舍如果转移区间是固定长度的滑动窗口单调队列 O(n) 更优只有区间端点动态变化时才需要线段树。7. 总结线段树优化 DP 的核心是把「区间最值查询」从 O(n) 降到 O(log n)从而把整体复杂度从 O(n²) 优化到 O(n log n)。它的适用场景是转移方程中需要查询动态区间的最值且区间端点随状态变化。掌握这一技巧需要同时熟悉线段树的建树、查询、更新三个基本操作并理解 DP 状态与线段树下标之间的映射关系。建议读者先手写一遍 LIS 的线段树版本再尝试区间调度类问题逐步体会这种优化的通用性。