企业官网建设流程全解析

1. 引言

动态规划（DP）是算法竞赛和工程面试中的常客，但当状态转移需要在一段区间内取最值时，朴素做法往往需要 O(n) 的扫描，导致整体复杂度上升到 O(n²) 甚至更高。线段树作为一种支持区间查询和单点修改的数据结构，恰好可以用来优化这类转移，把单次转移的代价降到 O(log n)。本文从原理出发，结合典型例题，讲解如何用线段树优化 DP。

2. 适用场景

并不是所有 DP 都需要线段树优化。通常，当状态转移方程满足以下特征时，可以考虑引入线段树：

• 区间最值查询：转移时需要从某个下标区间内取最大值或最小值，例如 dp[i] = max(dp[j]) + w(i)，其中 j 属于某个连续区间。
• 单点更新：每计算完一个 dp[i]，需要把它插入到线段树的对应位置，供后续状态查询。
• 值域较大：如果值域较小，可以用树状数组或单调队列；当值域较大且需要离散化时，线段树依然适用。

相比之下，如果区间是固定长度的滑动窗口，单调队列往往更优；如果只涉及前缀最值，树状数组或前缀数组就足够了。线段树的优势在于区间端点可以随状态动态变化，不受窗口长度限制。

3. 核心思想

线段树优化 DP 的核心思路可以概括为三步：

1. 建树：用线段树维护 dp 数组的区间最值（或区间和、区间乘积等），初始时把所有位置设为负无穷（求最大值时）或正无穷（求最小值时）。
2. 查询：计算 dp[i] 时，根据转移方程确定需要查询的区间 [L, R]，调用线段树的区间查询接口，在 O(log n) 时间内得到该区间的最值。
3. 更新：得到 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; vector<int> 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 的线段树版本，再尝试区间调度类问题，逐步体会这种优化的通用性。