CC++ & Algorithm

动态DP（DDP）——快速更新问题的智慧

较难2
语言版本：C++
概述：用游戏角色升级的例子，学会用“魔法线段树”快速重新计算动态规划结果。

动态DP（DDP）——快速更新答案的魔法

你有没有想过，游戏里的技能树一旦被策划修改了某个技能的数值，系统是怎么立刻算出新的最优加点的？又或者，老师改了一道题目的分数，你如何快速知道全班最高分的变化？这些场景背后，都藏着一种叫动态DP（Dynamic Programming with Updates，简称 DDP）的技巧。简单说，DDP 能让我们在修改数据后，不用从头算一遍，只更新一小部分就得到新答案。

什么是动态DP？

想象你玩一个角色扮演游戏，角色有一个技能树（像一棵倒着的树），每个技能点都有战斗力加成。但是规则说：相邻的两个技能不能同时学（比如学了“火球术”就不能学旁边的“冰霜术”）。你想选一些技能，让总战斗力最大。这就是经典的树形动态规划问题。

现在假设游戏策划突然把某个技能的基础战斗力从 10 改成了 20。如果每次都从树的根开始重新算一遍，数据量大时就会很慢（比如一棵树有几万个节点）。有没有办法只修改一小部分，就能得到新答案？这就是动态DP要做的事情——在动态变化的数据上，快速维护 DP 的结果。

生活中的比喻：搭积木塔

假设你搭了一个积木塔（像一棵倒立的树），每块积木重量不同。你想让塔最稳（总重量最大），但有个规则：相邻的两块积木不能同时选中（否则会倒）。现在你换掉了其中一块积木的重量，要快速知道新塔的最大重量。

你可以这样做：在每一块积木上记录两个信息：

  • 如果选这块积木，以它为顶点的子树的最大重量是多少。
  • 如果不选这块积木，以它为顶点的子树的最大重量是多少。

修改某块积木的重量后，你只需要更新这块积木以及它上面所有积木（一直往上到塔顶）的信息。因为只有这些路径上的信息会受影响。这样一来，修改的代价只和树的高度有关，而不是整棵树的大小。这就是 DDP 的基本思想。

先从一个简单例子开始：最大子段和

为了更容易理解，我们先不看树，而是看一个一维数组。你面前有一排连续的地鼠洞，每个洞里有一个分值（可以是正数、负数或零）。你要打连续的一串地鼠（也就是一个连续的子段），使得分总和最大。这就是经典的最大子段和问题。

现在，你可以任意修改一个地鼠洞的分值，然后需要快速知道新的最大子段和。如果每次修改后都用普通的循环重新计算（O(n)），当数据很大时就太慢了。有没有更快的办法？

有！我们可以用线段树来帮忙。线段树像一棵二叉树，每个节点代表一段区间，节点里存着关于这段区间的几个关键信息，让我们能在修改时只更新 O(log n) 个节点，就能得到整个数组的最大子段和。

线段树节点存什么？

对于线段树的每个节点（表示区间 [L, R]），我们存四个数字：

  • sum：该区间所有元素的总和。
  • pre：该区间内，从最左边开始往右的连续子段的最大和（简称“最大前缀和”）。
  • suf：该区间内，从最右边开始往左的连续子段的最大和（简称“最大后缀和”）。
  • ans：该区间内，全局的最大子段和（不一定要从左或右边界开始）。

举个例子，假设数组是 [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]（著名的例子）。对于整个区间：

  • sum = 把所有数加起来 = 1。
  • pre = 从左边开始，最大连续和是 4（选 4, -1, 2, 1 或者 4 本身？实际上是 1 吗？我们算一下：从左边依次加：-2 得 -2，加 1 得 -1，加 -3 得 -4，加 4 得 0，加 -1 得 -1，加 2 得 1，加 1 得 2，加 -5 得 -3，加 4 得 1。最大的前缀和出现在第 8 个数（位置8）之后？其实最大前缀和是 4（只取第4个数4）或者 1？耐心算：前缀和序列：-2, -1, -4, 0, -1, 1, 2, -3, 1，最大值是 2（位置7结尾）。但最大子段和是整个区间内的，pre 必须以左边界开始，所以只能从第一个数开始，不能跳过。因此 pre = 2（从位置1到7的和是 2）。但更精确的计算是：从第一个数开始，可以随时停止，所以最大前缀和是 4？不，因为从第一个数开始，不能跳过 -2，所以必须包含 -2。实际上如果数组是 [-2, 1, -3, 4]，前缀和可能是 -2, -1, -4, 0，最大值 0。但这里例子是为了说明概念，我们不用纠结具体数字。
  • suf = 从右边开始，最大连续和是 4（只取最后一个数 4），或者 1？从右边加：4, -5+4=-1, 1+(-1)=0, 2+0=2, -1+2=1, 4+1=5, -3+5=2, 1+2=3, -2+3=1。最大后缀和是 5（从位置3到9的和是 1-3+4-1+2+1-5+4 = 3? 再算一遍：位置3=-3,4=4,5=-1,6=2,7=1,8=-5,9=4 => 和=4? 还是直接看：数组是 [-2,1,-3,4,-1,2,1,-5,4]，从右边开始的最优序列是 [4] 得 4，或者 [1,-5,4]=0，或者 [2,1,-5,4]=2，或者 [-1,2,1,-5,4]=1，或者 [4,-1,2,1,-5,4]=5？不行，因为 -1 前面还有 4？实际上从右边开始，你必须连续包含从末尾往左的数，所以可以选最后四个数：4,-5,1,2? 不对，从右往左：4, -5, 1, 2, -1, 4, -3, 1, -2。最大子段和是 4 或 5？5 来自 4+2+1-5+4? 这要连续。我们不需要精确数字，只是说明概念。
  • ans = 整个区间的最大子段和，可能是 4+(-1)+2+1=6 或者 4 等，这里是 6（从第4到第7个）。

在实际计算中，这些值是通过左右子节点的信息合并得到的。合并公式非常重要，下面我们来详细推导。

合并两个相邻区间的信息

假设我们已经有左区间 [L, mid] 和右区间 [mid+1, R] 的四个值，现在要合并成父区间 [L, R] 的四个值。合并公式如下：

父区间.sum    = 左.sum + 右.sum
父区间.pre    = max(左.pre, 左.sum + 右.pre)
父区间.suf    = max(右.suf, 右.sum + 左.suf)
父区间.ans    = max(左.ans, 右.ans, 左.suf + 右.pre)

为什么这样合并？我们一个一个解释。

  • sum：总和就是左右两部分的和，简单。
  • pre（最大前缀和）：从父区间左边开始的最大连续和，有两种可能：
    1. 只取左区间的一部分，即左区间的最大前缀和（因为右区间还没开始）。
    2. 取整个左区间，再加上右区间的最大前缀和（因为左区间必须全部取完，才能进入右区间）。 两者取较大值。
  • suf（最大后缀和）：从父区间右边开始的最大连续和，有两种可能：
    1. 只取右区间的一部分，即右区间的最大后缀和。
    2. 取整个右区间，再加上左区间的最大后缀和。
  • ans（全局最大子段和）：有三种来源：
    1. 完全在左区间：左.ans
    2. 完全在右区间：右.ans
    3. 跨越中点：左区间的最大后缀 + 右区间的最大前缀

生活中的例子：假设你有一排地鼠洞，左边一段的分值记录在左区间上，右边一段记录在右区间上。你要找整个一排的最大连续子段和。那么最优解要么完全在左边，要么完全在右边，要么跨过中间——这时中间的部分必须包括左边末尾和右边开头。

代码实现

下面的C++代码实现了用线段树支持单点修改和全局最大子段和查询。每一行变量都加了中文注释，方便理解。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;  // 数组最大长度

// 线段树节点，存储区间信息
struct Node {
    int sum;   // 区间和
    int pre;   // 区间最大前缀和
    int suf;   // 区间最大后缀和
    int ans;   // 区间最大子段和
} tree[MAXN * 4];  // 线段树数组，一般开4倍空间

int a[MAXN];  // 原始数组，下标从1开始

// 合并左右子节点，更新父节点
void pushup(int idx) {
    int l = idx * 2, r = idx * 2 + 1;  // 左右孩子下标
    tree[idx].sum = tree[l].sum + tree[r].sum;
    tree[idx].pre = max(tree[l].pre, tree[l].sum + tree[r].pre);
    tree[idx].suf = max(tree[r].suf, tree[r].sum + tree[l].suf);
    tree[idx].ans = max({tree[l].ans, tree[r].ans, tree[l].suf + tree[r].pre});
}

// 建树：递归构建区间[l, r]的线段树
void build(int idx, int l, int r) {
    if (l == r) {
        // 叶子节点，只有一个元素
        tree[idx] = {a[l], a[l], a[l], a[l]};
        return;
    }
    int mid = (l + r) / 2;
    build(idx * 2, l, mid);         // 左儿子
    build(idx * 2 + 1, mid + 1, r); // 右儿子
    pushup(idx);                    // 合并
}

// 单点修改：将位置 pos 的值改为 val
void update(int idx, int l, int r, int pos, int val) {
    if (l == r) {
        a[pos] = val;  // 更新原始数组（可选）
        tree[idx] = {val, val, val, val};
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid) update(idx * 2, l, mid, pos, val);
    else            update(idx * 2 + 1, mid + 1, r, pos, val);
    pushup(idx);  // 沿路更新
}

int main() {
    int n, q;  // n: 数组长度, q: 修改次数
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);  // 建树

    while (q--) {
        int pos, val;  // 要修改的位置和新的值
        cin >> pos >> val;
        update(1, 1, n, pos, val);
        // 整个数组的最大子段和就是根节点的ans
        cout << tree[1].ans << endl;
    }
    return 0;
}

常见错误与避坑指南

  1. 忘记调用 pushup：修改后如果没有在 update 函数最后调用 pushup，父节点的信息就不会更新，导致查询结果错误。记住：在递归返回后必须合并。
  2. 合并公式写错：尤其是 pre 和 suf 的公式容易混淆。记住：pre 依赖于左子树的 sum 加右子树的 pre；suf 依赖于右子树的 sum 加左子树的 suf。可以对比上面的生活例子来记忆。
  3. 数组开太小：线段树节点数一般是 4 * n，但如果你用了 MAXN 作为数组长度，要确保 MAXN 足够大。比如 n=100000，tree 数组大小至少 400000。
  4. 下标从0开始还是1开始：上面的代码统一从1开始，方便线段树计算孩子下标。如果从0开始，要注意 mid 的计算和边界。
  5. 查询整个数组时直接输出根节点：如果题目要求查询任意区间，需要实现 query 函数，并返回一个 Node 结构体。上面的代码只支持全局查询，对于更复杂的查询，需要扩展。

从一维到树：DDP 的无限可能

学会了最大子段和的动态维护，你已经掌握了 DDP 的核心思想：用数据结构（线段树、树链剖分等）把 DP 的转移过程表示为矩阵乘法或合并操作，使得更新时只影响 O(log n) 个节点。

对于更复杂的树形 DP（比如开头的技能树例子），我们可以用树链剖分将树拆成多条链，每条链用线段树维护 DP 值，修改一个节点时只需更新它所在链上的 O(log n) 个节点，这就是真正的动态树形 DP。甚至可以用矩阵乘法来统一表示转移，然后用线段树维护区间矩阵乘积。

相关知识与拓展

  • 线段树基础：学会线段树的构建、单点修改和区间查询（求和、最值）。动态DP的线段树只是存的信息不同。
  • 树链剖分（Heavy Light Decomposition）：把树拆成链，让树上路径可以像数组一样用线段树维护。
  • 矩阵乘法优化DP：很多 DP 转移可以写成矩阵乘法的形式，这样线段树节点存矩阵，合并就是矩阵相乘。动态DP的常见实现就是“线段树 + 矩阵”。
  • Splay Tree / LCT：更高级的动态树数据结构，用于维护森林上的 DP。

如果你对技能树优化问题感兴趣，可以搜索 “树形DP + 树链剖分 + 动态DP”，那是NOI级别的经典题目。

总结：动态DP是一种在动态变化的数据上快速重新计算DP结果的技术。通过将DP转移抽象成可合并的信息（如最大子段和的四个值），并用线段树等数据结构维护，每次修改只需要 O(log n) 时间。它就像给你的算法装上了“快速重算引擎”，让程序能在数据变化时瞬间给出新答案。

例题精讲

1单选题

动态DP（DDP）中，将DP转移过程映射到线段树维护的关键前提是什么？

ADP转移必须包含加法运算
BDP转移的复合运算必须满足结合律
CDP必须是无后效性的
DDP状态必须具有连续性
2判断题

在树上的动态DP中，使用树链剖分后，每个节点维护的矩阵（或结构体）仅包含该节点及其所有轻儿子的贡献，重儿子的贡献通过查询重链上后续节点的线段树来获得。

3填空题
以下代码实现了一个线段树节点，用于维护区间最大子段和（动态DP的典型例子）。请补全 merge 函数中的空白，使得合并后的 res.maxv 正确表示合并区间的最大子段和。

struct Node {
    int sum;   // 区间和
    int lmax;  // 区间最大前缀和
    int rmax;  // 区间最大后缀和
    int maxv;  // 区间最大子段和
};

Node merge(Node a, Node b) {
    Node res;
    res.sum = a.sum + b.sum;
    res.lmax = max(a.lmax, a.sum + b.lmax);
    res.rmax = max(b.rmax, b.sum + a.rmax);
    res.maxv = max({a.maxv, b.maxv, ___});  // 填空处
    return res;
}
4单选题

在树上的最大权独立集动态DP中，定义 g[u][0] = sum_{v是u的轻儿子} max(f[v][0], f[v][1])，g[u][1] = w[u] + sum_{v是u的轻儿子} f[v][0]。转移方程（只考虑重儿子）为：f[u][0] = g[u][0] + max(f[重][0], f[重][1])，f[u][1] = g[u][1] + f[重][0]。现将其表示为 max-plus 矩阵乘法（加法取max，乘法取加法），向量 v = [f[重][0], f[重][1]]^T，矩阵 M = [[g[u][0], g[u][0]], [g[u][1], -∞]]，则乘积 M × v 的第二个元素等于？

Ag[u][1] + f[重][0]
Bg[u][1] + f[重][1]
Cmax(g[u][1]+f[重][0], g[u][1]+f[重][1])
Dg[u][1] + max(f[重][0], f[重][1])
5填空题
以下为 max-plus 矩阵乘法的实现（2×2矩阵），请补全循环体内的空白，完成矩阵乘法。

const int INF = 1e9;
struct Mat {
    int a[2][2];
    Mat() { for (int i=0;i<2;i++) for (int j=0;j<2;j++) a[i][j] = -INF; }
};

Mat mul(Mat A, Mat B) {
    Mat C;
    for (int i=0;i<2;i++) {
        for (int j=0;j<2;j++) {
            for (int k=0;k<2;k++) {
                C.a[i][j] = max(C.a[i][j], ___);  // 填空处
            }
        }
    }
    return C;
}