卡牌DP优化实战：从O(n²)到权值线段树

有一次我盯着一道标题写着“卡牌对战游戏（DP+权值线段树）”的题卡了大半个晚上。卡点不在 DP 理解上，而是当我把“每张卡可以选或跳过、且出战序列攻击力严格递增”的状态转移写出来后，发现复杂度直接 O(n²)。后来我真正把“权值线段树”这个名词拆开，才发现它根本不是什么复杂的东西：不过是在值域上开线段树，让 DP 的每次转移都从“扫一遍历史卡牌”变成一次 O(log n) 的值域查询。这篇文章就是我当时从懵到通透的完整过程。适合正在刷算法题、想搞懂“为什么卡牌类 DP 要配权值线段树”的读者，也适合自己做卡牌游戏底层数值系统、需要处理在线值域统计的开发者。

1. 那晚我为什么会被 O(n²) 卡住：先还原一道卡牌题的完整规则

1.1 一个马上能复现的选卡规则

假设有这么一套卡牌对战规则：有 n 张卡牌按给定顺序摆在桌面上，每张卡有两个属性，一个是攻击力 atk，一个是收益 score。你从左到右一张张翻牌，每翻到一张卡，可以选择把它收进“出战序列”，也可以选择跳过。唯一的限制是：出战序列中，卡牌的攻击力必须严格递增。

为什么攻击力要严格递增？用卡牌游戏的语境说就是“连击不能断，序列一旦出现逆势就士气崩坏”。但抛开剧情设定，这个限制非常像经典的“带权最长上升子序列”——你要在保持原顺序的前提下选出一个子序列，让攻击力序列严格上升，同时让得分总和最大。

举个例子，这个例子我先放在这，后面手算代码时还会用到：

肉眼看一下，选择第 2 张（atk=1, score=5）、第 4 张（atk=2, score=6）、第 5 张（atk=4, score=8）是可行的，因为 1 < 2 < 4，总收益是 19。注意第 4 张虽然和第 1 张攻击力相同，但第 1 张在前面且攻击力不比第 2 张大，所以不能把第 1 张插进这个序列；而第 4 张攻击力等于 2，能放在 1 和 4 之间。

这个规则看着像摸牌策略，实际上是一个典型的值域约束最优化问题。下面进入状态设计。

1.2 DP 公式：以哪张卡结尾最干净

设dp[i]表示“以第 i 张卡作为出战序列最后一张卡时，能获得的最大收益”。如果不选任何卡，收益是 0，所以空状态是一个天然的前驱。转移其实一句话就能写完：

dp[i] = score[i] + max(0, max(dp[j])) 其中 j < i 且 atk[j] < atk[i]

这个公式的含义是：我以第 i 张卡结尾，那它前面一定接了一个攻击力比它小、原顺序比它靠前的卡牌状态。如果前面什么都没有，那就从空状态直接选第 i 张，得到score[i]。答案就是所有dp[i]的最大值，同时不能低于 0，因为你可以一张牌都不选。

朴素写法非常直接：

long long ans = 0; for (int i = 1; i <= n; i++) { dp[i] = cards[i].score; for (int j = 1; j < i; j++) { if (cards[j].atk < cards[i].atk) { dp[i] = max(dp[i], dp[j] + cards[i].score); } } ans = max(ans, dp[i]); }

这段代码没错，但它需要遍历所有历史卡牌。n 小的时候无所谓，一旦 n 到 10^5 级别，O(n²) 就是灾难。我那个晚上就是因为随手写了个双循环，然后看着数据范围陷入沉思：明明状态设计没问题，为什么就是跑不动？

问题的核心在于：每一次转移，都浪费在了“扫描所有历史卡牌”上。而实际上，真正有用的信息只有一个——历史已处理的卡牌中，攻击力小于atk[i]的那些卡，它们的dp最大值是多少。

1.3 把“扫历史”变成“查值域”

如果能维护一个数组best[value]，表示“历史中所有攻击力恰为 value 的卡牌，作为结尾时的最大 dp 值”，那么当前卡牌的转移就变成了：

dp[i] = score[i] + max(best[1], best[2], ..., best[atk[i] - 1])

这就是一个值域前缀最大值查询。处理完第 i 张卡后，再更新：

best[atk[i]] = max(best[atk[i]], dp[i])

于是问题从一个“历史序列扫描问题”变成了一个“值域区间查询问题”。而能在值域上做单点更新、前缀/区间查询的数据结构，最经典的就是权值线段树。这个转变，就是标题里“DP + 权值线段树”的底层逻辑。

2. 权值线段树不是线段树的“权值版”，它的下标是攻击力本身

2.1 同样是递归分治，世界观不一样

很多读者第一次看到“权值线段树”时会以为它只是线段树加了个权值数组。其实它和普通线段树的核心区别在于下标的含义完全不同。

普通线段树的下标是“数组位置”。比如一棵管[l, r]区间的节点，代表的是原数组第 l 到第 r 个元素的聚合信息。而权值线段树的下标是“值域”，管[L, R]的节点，代表的是所有数值落在[L, R]范围内的元素的聚合信息。

所以权值线段树其实是“把数值当作坐标”的线段树。它天然适合回答“有多少个数小于 x”“某个值域内的最值是多少”这类问题。卡牌游戏里的攻击力排序，恰好就需要这种能力。

2.2 聚合值是可以定制的：这一题存的是 max

权值线段树最常见的形态是“值域内有多少个数”，也就是每个节点维护一个cnt，插入一个数就把对应路径上的cnt加一。但这不是唯一用法。

我们的 DP 转移要求的是“攻击力小于当前值的所有历史状态中，dp 的最大值”。所以树里每个节点应该存的是：这个值域范围内，所有已知 dp 值的最大值。

具体地说，在扫描过程中，每遇到一张卡，我们都会拿到它对应的dp[i]。假设这张卡的攻击力是 value，那我们就在值域位置 value 上做一次“取最大”的更新：

best[value] = max(best[value], dp[i])

然后一棵权值线段树用来维护这个best数组的区间最大值。查询“攻击力小于 atk[i] 的最优历史状态”，就等价于查询值域区间[1, atk[i]-1]内的最大值。

这里要特别注意一点：权值线段树只是提供“按值域分治的容器”，节点里存什么聚合值完全由问题决定。卡牌题可以存 max，排名题可以存 cnt，有些场景还能存 gcd、次数和、前缀和之类的信息。先用 cnt 理解权值线段树，再用 max 解决 DP 问题，是两条不同的熟悉路径。

2.3 离散化：攻击力从 1e9 变成最多 n 个排名

卡牌的攻击力范围可能很大，从 1 到 10^9 都可能。如果直接按值域开线段树，根节点的管辖区间大到离谱，静态数组根本开不下。所以要先做离散化。

离散化的流程很简单：

1. 收集所有卡牌的攻击力值。
2. 排序、去重。
3. 每个攻击力用它在去重数组中的下标替代。

比如攻击力集合是{100, 3, 500, 3}，排序去重后变成[3, 100, 500]。3 对应下标 0，100 对应下标 1，500 对应下标 2。之后所有值域操作都在这个压缩后的下标上进行。

具体到代码里，我会这样做：

sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); for (int i = 0; i < n; i++) { cards[i].rk = lower_bound(vals.begin(), vals.end(), cards[i].atk) - vals.begin(); }

查询严格递增的前驱时，如果当前卡的rk = r，那么所有攻击力严格小于它的卡，对应的离散化下标范围就是[0, r-1]。如果r = 0，说明它已经是当前值域里最小的攻击力，没有更小状态，前驱只能为空状态。

离散化这一步看着简单，却很容易埋雷。所有要用到的值必须一次性收集完再统一离散化，绝对不能边处理边往里塞值。后面第 5 章我会专门说这个雷。

2.4 严格递增的关键纪律：先查询，后更新

用权值线段树做这个 DP，有一个非常容易被忽略的细节：一定要先查询前驱状态，再把自己插入树中。

原因在于“攻击力严格递增”。如果先更新再查询，当前卡自己刚插入的状态也会被查出来，等于允许一张卡作为自己的前缀，这在严格递增规则下是不合法的。更隐蔽的是，如果两张攻击力相同的卡一前一后，先更新后查询会让后面的卡从前面那张同攻击力的卡转移，同样破坏严格性。

正确的顺序永远是：

1. 查询[0, rk-1]的最优历史状态，得到bestPrev。
2. 计算dp[i] = bestPrev + score[i]。
3. 把dp[i]更新到rk位置。

如果是非严格递增，也就是允许atk[j] <= atk[i]，那查询区间改成[0, rk]即可，但“先查后更”的纪律最好不要改。因为就算允许相等的攻击力，先更后查也会让同一张卡自己转移自己，逻辑上还是会出错。

3. 一份可以直接抄作业的 C++ 实现，我一行行说为什么这么写

3.1 代码的整体节奏

这题的实现步骤可以拆成四块：读入卡牌数据、对攻击力离散化、建一棵空线段树、顺序扫描并查询更新。前两步是预处理，后两步是核心 DP。

为什么必须先把所有攻击力读进来再离散化？因为离散化需要一个全局的去重数组。如果只处理到一半再去查“小于当前值的攻击力有哪些”，无法确定值域范围，也就没法确定线段树该建多大。所以输入全部读完，别偷懒。

3.2 完整代码

#include <bits/stdc++.h> using namespace std; const int MAXN = 200005; struct Card { int atk; long long score; int rk; // 离散化后的攻击力排名，0-based }; struct Node { long long mx; // 当前值域区间内的最大 dp 值 } tree[MAXN << 2]; int n; void pushUp(int p) { tree[p].mx = max(tree[p << 1].mx, tree[p << 1 | 1].mx); } void build(int p, int l, int r) { tree[p].mx = 0; // 初始没有任何历史状态，空状态收益为 0 if (l == r) return; int mid = (l + r) >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); } long long query(int p, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return tree[p].mx; int mid = (l + r) >> 1; long long res = 0; if (ql <= mid) res = max(res, query(p << 1, l, mid, ql, qr)); if (qr > mid) res = max(res, query(p << 1 | 1, mid + 1, r, ql, qr)); return res; } void update(int p, int l, int r, int pos, long long val) { if (l == r) { tree[p].mx = max(tree[p].mx, val); return; } int mid = (l + r) >> 1; if (pos <= mid) update(p << 1, l, mid, pos, val); else update(p << 1 | 1, mid + 1, r, pos, val); pushUp(p); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; vector<Card> cards(n); vector<int> vals; vals.reserve(n); for (int i = 0; i < n; i++) { cin >> cards[i].atk >> cards[i].score; vals.push_back(cards[i].atk); } sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); for (int i = 0; i < n; i++) { cards[i].rk = lower_bound(vals.begin(), vals.end(), cards[i].atk) - vals.begin(); } int m = vals.size(); build(1, 0, m - 1); long long ans = 0; for (int i = 0; i < n; i++) { long long bestPrev = 0; if (cards[i].rk > 0) { bestPrev = query(1, 0, m - 1, 0, cards[i].rk - 1); } long long cur = bestPrev + cards[i].score; ans = max(ans, cur); update(1, 0, m - 1, cards[i].rk, cur); } cout << ans << "\n"; return 0; }

3.3 手算样例验证

回到第 1 章的样例。攻击力集合是{2,1,3,2,4}，排序去重后为[1,2,3,4]，所以离散化下标分别是：atk=1 对应 0，atk=2 对应 1，atk=3 对应 2，atk=4 对应 3。

按顺序扫描：

• 第 1 张卡：atk=2, rk=1。查询[0,0]得到 0，cur = 1，更新位置 1 为 1。
• 第 2 张卡：atk=1, rk=0。没有更小前缀，cur = 5，更新位置 0 为 5。
• 第 3 张卡：atk=3, rk=2。查询[0,1]，历史最大值是 5，cur = 7，更新位置 2 为 7。
• 第 4 张卡：atk=2, rk=1。查询[0,0]，得到 5，cur = 11，更新位置 1：原来的 1 变成 11。
• 第 5 张卡：atk=4, rk=3。查询[0,2]，三个位置分别是 5、11、7，最大值是 11，cur = 19，更新位置 3 为 19。

最终答案 19，对应序列：第 2 张（atk=1，收益 5）→ 第 4 张（atk=2，收益 6）→ 第 5 张（atk=4，收益 8）。

这组数据特意放了两个攻击力相同的卡，就是为了看第 4 张卡能不能从第 1 张卡转移。正确答案是不能，因为选择第 2 张后再选第 4 张可以获得更高的收益；而第 4 张如果从第 1 张转移，收益只有 1+6=7，远远不够。代码里的“先查后更”保证了相同攻击力不会互相转移。

3.4 复杂度与内存

离散化排序一次 O(n log n)，每张卡做一次查询、一次更新，都是 O(log n)。整体时间复杂度 O(n log n)，空间复杂度 O(n)。n 到 10^5 级别完全没问题。

树上的每个节点只存一个long long，静态数组开MAXN << 2就够了。注意卡牌收益可能很大，用 int 会在答案超过 21 亿时溢出，所以 DP 值和答案我都用long long存。

4. 把卡牌规则改一改：区间步长、双属性牌组、在线发牌又怎么办

4.1 规则一：连击要求从“严格递增”变成“攻击力差不大于 K”

很多卡牌游戏里，连击并不是只能接更大的牌，而是要求下一张牌的攻击力和当前牌的攻击力差值不超过 K，比如“只能连段差在 50 以内的卡”。

这时候转移条件从atk[j] < atk[i]变成了atk[i] - K <= atk[j] < atk[i]。也就是说，要查询的历史状态不再是一个前缀[0, rk-1]，而是一个值域区间。

用权值线段树做这个改动非常自然。先在离散化前的原值数组上算边界：

int L = lower_bound(vals.begin(), vals.end(), cards[i].atk - K) - vals.begin(); int R = lower_bound(vals.begin(), vals.end(), cards[i].atk) - vals.begin() - 1; long long bestPrev = 0; if (L <= R) { bestPrev = query(1, 0, m - 1, L, R); }

注意这里的L不能直接用离散化后的rk - K。因为离散化会丢弃原值之间的实际距离，比如原值 1 和 100，离散化后下标只差 1，但原值差 99。K=50 时，rk-K的概念根本不对，必须用lower_bound在原值集合里找“第一个不小于 atk[i]-K 的位置”。

这种时候权值线段树的优势就体现出来了：它可以很方便地做任意区间最值查询。树状数组做前缀最值很顺手，做任意区间最值就要绕不少弯子。

4.2 规则二：卡牌带属性，每种属性独立成长

再复杂一点：每张牌除了攻击力和收益，还带一个属性 type，比如水、火、木。规则要求同一个属性内的卡牌攻击力必须严格递增，不同属性互不干扰。这时候我们需要为每个属性单独维护一棵权值线段树。

如果属性数量很多，直接开 M 棵静态树会爆空间。更好的做法是动态开点：只在查询或更新时创建路径上的节点，不存在的节点相当于没有历史状态。

动态开点线段树的节点结构长这样：

struct Node { int lc, rc; long long mx; } tr[MAXN * 20]; int root[MAXM]; // 每个属性一棵树，存根节点下标

每次 update 时，如果要往下走的路还没有节点，就++tot创建新节点。查询时遇到空节点直接返回 0。这样总节点数是所有更新操作经过的路径长度之和，大概 O(n log m)，比 M 棵完整线段树省非常多。

这种扩展是权值线段树真正值钱的地方。静态数组版只是一个基础形态，一旦题目变成多棵、持久化、在线插入，动态开点会变成常规手段。

4.3 规则三：真正在线发牌，不再预先离散化

前面几版都要求先读入全部数据做离散化。如果场景变成“一张一张发牌，每发一张立刻算出当前最优收益”，而攻击力范围又很大，那静态离散化就不合适了。

这时候可以完全放弃离散化，直接用动态开点权值线段树，把攻击力当作真正的线段树下标。比如值域是[1, 10^9]，我们只在根节点记录这个范围，查询时递归下钻，遇到空节点返回 0，更新时动态创建路径节点。

这种做法本质上是用空间换灵活性。每次操作 O(log(值域))，在 10^9 范围下也才 30 层左右，完全能接受。很多在线卡牌系统的数值统计，用这种方案可以做到真正的“来一张牌，处理一张”。

5. 这些坑我每种都踩过：离散化边界、更新顺序与树的大小

5.1 裸的 rk - 1 在什么时候会翻车

严格递增版本里，query(0, rk - 1)没毛病。因为我只需要判断“值域排名小于当前排名”，所有攻击力严格小于当前卡的卡，排名一定更小；而离散化后的排名是连续的，所以[0, rk-1]能完整覆盖。

但一旦规则变成“差值不超过 K”，直接用rk - K当作查询左端点就是典型错误。离散化丢失了原值的距离信息，K 是一个原值意义上的长度，不是排名意义上的跨度。这种情况下必须用lower_bound(vals.begin(), vals.end(), atk[i] - K)去原值数组中重新定位。

这也是我想强调的一点：离散化只是把值域“压缩”成排名，不代表排名相邻的两个值在原值上也相邻。需要做原值范围查询时，边界一定要回到原值维度算。

5.2 先查询后更新，这条纪律不能省

我见过不少写法，图省事把查询和更新写成：

update(1, 0, m - 1, rk, cur); bestPrev = query(1, 0, m - 1, 0, rk - 1);

这种顺序一出问题就非常隐蔽。举一个反例：两张牌的攻击力都是 2，收益分别是 10 和 5。严格递增规则下，正确答案是选第一张得到 10，第二张不能接在第一张后面，因为攻击力相等，所以答案应该是 10。

但如果先更新后查询，第二张卡先把自己更新进树里，再查询[0, rk-1]时，因为rk=1，查询范围是[0,0]，本身不包含自己，所以这个例子还看不出来。更危险的是非严格递增时把查询范围写成[0, rk]，那就会发生“自己从自己转移”的严重逻辑错误。

所以我的习惯是：不管严格还是非严格，都坚持“查询 → 计算 → 更新”的顺序，把根上的逻辑错误直接消灭在顺序里。

5.3 初值到底用 0 还是 -inf

这题里，空状态可以看作“一张不选，收益为 0”，所以线段树初始化为 0 是合理的。查询结果至少是 0，cur = bestPrev + score[i]最差就是score[i]，表示从空状态直接选当前卡。

但有一个前提要跟题意对齐：如果收益 score 可能为负数，且题目允许你一张牌都不选，那答案应该是 0。代码里ans的初始值就是 0，所以最终输出不会变成负数最大值。

如果题目改成“必须至少选一张卡”，那空状态不可用，树的初值就应该设为-INF，并且要对所有从空状态出发的转移做特殊处理。不过大多数卡牌题都不会设定“必须选卡”，所以 0 是更常用的选择。

5.4 静态树与动态开点的选择

我自己的选择标准很简单：

• 只有一个值域维度，且可以离线离散化：用静态数组版，代码短，常数小。
• 多个属性多棵树：用动态开点，否则空间会变成 M 倍。
• 真正在线、值域范围大：用动态开点，直接拿原值当下标。
• 需要持久化、版本回溯：用动态开点，每个历史版本单独存根节点。

动态开点看起来复杂，其实就是把原来“提前建好整棵树”改成“用到哪建到哪”，核心递归逻辑几乎没变。第一次写的时候容易忘掉空节点判断，但只要在 query 开头加一句“当前节点为空则返回 0”，在 update 里“孩子为空则新建”，基本就稳了。

5.5 从权值线段树到树状数组：什么时候其实可以更简单

如果题目只是单纯的前缀最大值加单点更新，树状数组确实更简洁。比如这题的严格递增原版，用一个树状数组维护前缀最大值就够了，代码还能短一截。

那为什么标题要点名“权值线段树”？因为现实中卡牌题往往会在你做完基础版之后立刻加变化：区间限制、多属性、动态插入、历史版本。每加一个变化，树状数组的可维护性就下降一点，而线段树那一套“值域区间递归分治”的框架始终没变。

既然刷到了这一类题，我建议还是把权值线段树写熟。它不只是这一道题的加速器，而是一套值域统计的通用框架。以后看到“卡牌 + 属性阈值 + 最优状态 + 值域查询”这种组合，你会条件反射地想到它，而不是每次都重新从零推导。

最后再补一个我自己养成的习惯：拿到任何“卡牌对战”类题目，先别急着写 DP，先把所有属性值域列出来，想清楚每次转移到底在查什么区间。很多看起来唬人的优化，其实都只是在回答同一个问题——到当前卡为止，比我小的那些卡里，哪个状态最好。把这个问法想清楚，权值线段树自然就冒出来了。