线段树优化 DP 吗

· · 算法·理论

本文主要介绍几类线段树和树状数组优化动态规划的方法。

本文的理论部分比较简单，所以主要以题目讲解为主。

Part 0. 前置知识

Part 1. 属性在一个区间的进行转移

这是讨论的是形如 f_i=Y(i)+\max\limits_{j<i,P(j)\in[L(i),R(i)]}\{X(j)\} 或者 f_i=Y(i)+\sum\limits_{j<i,P(j)\in[L(i),R(i)]}X(j) 的方程，其中 P(i),L(i),R(i),X(i),Y(i) 都是关于 i 的一个函数。

一个显然的优化是：以 P(j) 为下标建立线段树（可能需要离散化），每次在线段树上区间查询进行转移。如果是求和或者取前缀 \max，也可以用树状数组代替。

常见的模型有最长上升子序列以及它的各种扩展。

例 1. 上升子序列

题意描述：给定一个长度为 n 的序列 a，求严格上升子序列数量对 10^9+7 取模的结果。两个子序列不同，当且仅当存在至少一个数在原序列中的位置不同。n\leq 10^5,1\leq a_i\leq 10^9。

设 f_i 表示以 i 结尾的上升子序列数量，则转移方程为：

f_i=1+\sum_{j<i,a_j<a_i}f_j

可以使用树状数组进行优化：对 a 进行离散化，设 c_x=\sum\limits_{j<i,a_j=x}f_j，表示当前讨论过的位置中，每个 a_j 的 f 值之和，用树状数组维护它的前缀和。

对于 i，f_i=\sum\limits_{x<a_i}c_x+1，用树状数组求前缀和，然后再用 f_i 更新 c 数组。

时间复杂度 O(n\log n)。

例 2. 书本分配

题意描述：给定一个长度为 n 的序列 a，和正整数 k，你需要找到 a 的一个前缀分为 k 段，每段的权值是这段的 a 之和，最小化这 k 段权值的最大值。n\leq 10^5,-10^9\leq a_i\leq 10^9。

最小值最大，考虑二分答案。

容易发现，如果存在一种方案使分成 k+1 段满足每段的和都不超过 x，则一定存在 k 的方案，只需要去掉最后一段就行了。所以只需要求最大的段数。

设 S 为 a 的前缀和数组，f_i 表示前 i 个最多能分的段数，则

f_i=1+\max_{j<i,S_j\leq S_i-x}\{f_j\}

显然是一个前缀最大的转移，可以离散化加树状数组优化。

时间复杂度 O(n\log_n\log_V)，其中 V 为二分的值域。

code。

小结

看到区间限制，很容易想到用线段树或者树状数组优化。

Part 2. 把状态按阶段拍到线段树上

有时状态为 f_{i,j}，第 i 个阶段的状态 f_{i,j} 可以 O(1) 从第 i-1 个阶段的状态转移过来，那可以考虑用一棵线段树维护当前阶段状态的值。

一般，如果可以划分成几个区间进行贡献计算，则可以尝试线段树优化。

思考时可以把每个阶段分为几个步骤，把每个步骤在线段树上需要进行的操作考虑清楚，特别注意边界情况，方便思考和编码。

例 3. 洛谷 P8476 「GLR-R3」惊蛰

首先，所有在 b 中出现的值一定都在 a 中出现过，所以将 a 离散化，设 s 表示 a 中不同数的数量，第 k 大数为 x_k。

可以列出朴素的 DP 状态 g_{i,j} 表示考虑前 i 个数，最后一个数是 x_j 的最小代价，则方程为 g_{i,j}=\min\limits_{k=j}^s\{g_{i-1,k}+f(a_i,x_k)\}。

可以用前缀和优化，或者定义状态为 g_{i,j} 表示考虑前 i 个数，最后一个数大于等于 x_j 的最小代价，则 g_{i,j}=\min\{g_{i-1,j}+f(a_i,x_k),g_{i,j+1}\}。答案是 g_{n,1}。时间复杂度 O(n^2)。

设第 i 个数是第 k 小，则需要依次进行以下操作：

考虑把状态拍到线段树上。

对于第一个操作和第二个操作的 $-x_k$，是区间加一个常数。 对于第二个操作的 $+x_j$，区间中每个点加这个点的权值，相当于是一个单调的序列加上另一个单调的序列，则不管是加之前还是加之后，最大值都会取区间末尾元素，最小值都会取区间开头元素，所以可以直接加对应的值。 时间复杂度 $O(n\log n)$。 [code](https://www.luogu.com.cn/paste/r9nspllp)。 # Part 3. 与区间有关的 一些题目的会给定一些区间（或者其它条件转换成区间），可以先对区间进行处理，如：按左端点或右端点排序，或者去掉被包含的区间，然后思考是否能够 DP 并进行优化。 ## 例 4. [AT_dp_w Intervals](https://www.luogu.com.cn/problem/AT_dp_w) 首先按右端点排序，设计状态 $f_{i,j}$ 表示考虑前 $i$ 个点和 $r_i\leq i$ 的区间、最后一个是 $0$ 的位置是 $j$（没有 $0$ 则 $j=0$）的最大价值。 不难得到转移方程： $$f_{i,j}= \begin{cases} \max\limits_{k=0}^{i-1}\{f_{i,j},0\} & i=j\\ f_{i-1,j}+\sum\limits_{r_k=i,l_k>j}w_k & i\ne j \end{cases} $$ 压掉 $i$ 这维，可以用这个过程计算： - 求 $f_i=\max\limits_{k=0}^{i-1}\{f_j,0\}$； - 枚举 $r_k=i$，$\forall0\leq j<l_k,f_j\gets f_j+c_k

直接用线段树维护区间加、区间和即可。时间复杂度 O(n\log n)。

记得开 long long，特别是线段树的函数。

code。代码中用 vector 储存所以 r_j=i 的 (l_j,w_j) 来代替排序。

例 4.5 洛谷 P9871 [NOIP 2023] 天天爱打卡

与上面一题极类似，主要区别在于离散化。

注意到在上面的限制条件中，除非存在 k 满足 j=l_k-1 或 j=r_k，都会有 f_{i,j}=f_{i,j+1}，另一种理解方式是把闭区间改为左开右闭区间，则只需要将 r_i,l_i-1 离散化即可。

例 5. 洛谷 P2605 [ZJOI2010] 基站选址

对每个村庄，二分求最左边和最右边能覆盖到它的基站，则覆盖到这个村庄的基站是一个区间，问题转化为：的有 n 个区间和 n 个点，选择不超过 k 个点，选择第 i 个点的代价是 c_i，如果一个区间内的点都没有被选择，付出 w_i 的代价，最小化代价。

转移方程和优化方法与例 4 比较相似，只是多了一个阶段。时间复杂度 O(nk\log n)。

此外，这题还可以用 wqs 二分进一步优化。

设 F(x) 表示选择 x 个区间的最小代价，则 F(x) 是下凸函数，其中一种理解方式是：刚开始会选择贡献比较大的区间，且后面选择的区间因为有重叠，贡献会比较小。

设 G(p) 表示斜率为 p 的直线与 F 的切点横坐标，分：

同时，斜率 p 的实际意义是：每个点选择的代价增加 p。

在 DP 时多记录一个选择的点数即可。

时间复杂度 O(n\log V\log n)。

code。

例 6. AT_[ABC262EX] Max Limited Sequence

考虑一个弱化版：给定 m 个区间 [l_i,r_i]，且 \bigcup[l_i,r_i]=[1,n]，求长度为 n 的满足 \max\limits_{i=l_i}\limits^{r_i}\{a_i\}=X 的非负整数序列 a 数量。

首先将区间按左端点由小到大排序，然后去掉所有包含其它区间的区间，因为如果包含的区间满足条件，则它一定也满足条件。

设 f_{i,j} 表示考虑前 i 个点和 r_i\leq i 的区间，最后一个值为 X 的点是 j 的方案数，对于第 i 个点，决策有选 X 和不选 X 两种：

可以用一个支持单点加、区间乘、区间求和的线段树实现。

然后回到原问题。把区间按权值排序由小到大、权值相同的按左端点排序，对于一个区间，权值比它小的区间包含的位置，一定不会成为它的最大值，所以可以找出没讨论的区间中，排序最靠前的，然后依次加入没有讨论的区间，如果这个区间与当前的区间并交集非空，则把它加入，用它们的有效部分跑上面的算法，并把最后答案乘上跑出的答案，最后把它们包含的点删除。

如图，绿色区间权值为 1，蓝色区间权值为 2，则会划分为图中的 3 组依次进行 DP。同时蓝色区间的有效部分是紫色部分。注意，我们视作把蓝色部分删掉并把每段拼起来剩余的部分为有效部分，所以虽然最下面的一个区间有两段紫色，把它们拼起来之后只算作一个区间。

可以用并查集和树状数组实现删除和查询在删除后区间实际包含的位置。

时间复杂度 O(n\log n)。

code。

小结

如果发现题目的贡献或者限制跟区间有关，可以尝试按端点排序（或者分类），有时候可以使限制的区间互相不包含，然后再进行思考。

Part 4. 与坐标有关的

有一些数量关系，如果弄成元组的形式，并转化为坐标，就可以发现一些很优美的性质，方便数据结构维护，比如阶梯形。可以设计出 DP 方程并进行优化。

例 7. 分类

n$ 个元素有属性 $a_i,b_i,x_i,y_i$，将它们分为 $P,Q$ 两个集合，满足不存在 $i\in P,j\in Q$ 使得 $a_i\ge a_j,b_i\le b_j$，最大化 $\sum\limits_{i\in P}x_i+\sum\limits_{i\in Q}y_i

。1\leq n\leq 10^5，1\leq a_i,b_i,x_i,y_i\leq 10^9。

注意到二元组 (a_i,b_i) 存在限制，所以考虑转化为坐标：

如果把点 A,B 都划分在集合 Q，为了满足条件，则它们左上部分，即所有蓝色阴影部分（包括蓝线）都必须属于 B 集合。

也就是说，如果把一个合法方案的 Q 的点的右上部分框出来，则这里面没有一个点属于 P 集合。所以，存在一条阶梯状的分界线，使得右上方和线上分到 Q 集合，左下方分到 P 集合。

那这样就比较简单了，先将点按 a_i 从大到小排序，再按 b_i 从大到小排序（a 相等时，如果 b 较大的点选择 Q 集合，那较小的点也是 P 集合）。设 f_{i} 表示 i 之前的点，将 i 分到 Q 的最大价值，设 w(i,j)=\sum\limits_{k=j}^i[b_k\ge b_j]y_k+[b_k< b_j]x_k，表示将 (j,i) 这段点在 j 左上方分为 Q 集合，右下方分为 P 集合的最大价值，则 f_i=\max\limits_{j<i,b_j>b_i}\{f_j+w(i,j)\}。

计算 f_j+w(i,j) 最大值。设 g_k 表示 \max\limits_{b_j=k}\{f_j+w(i,j)\}，则对于新加入一个点 i：

离散化并用线段树维护 g 数组，可以实现转移。时间复杂度 O(n\log n)。

code。

例 8. AT [ARC101F] Robots and Exits

如果一个机器人只有左边或者只有右边有出口，则它必须选择这个出口，所以忽略这样的机器人。对于其它机器人，只可能从离它最近的左边出口或者右边出口出去。

用 (l,r) 描述一个机器人，表示它离左边出口的距离和离右边出口的距离，画到坐标系上，则：

不难发现，如果 (l_i,r_i) 在 y 轴上被删除，所有的 l_j\ge l_i,r_j\leq r_j 也必须在 y 轴被删除。于是，这里的同样满足上一道题的阶梯性质。

把点按 l 从小到大排序，l 相同的按 r 从大到小排序，考虑求拐点序列方案数，即不被其它选 y 轴的点左上角的点，设 f_i 表示最后一个拐点是 i 的方案数，则 f_i=\sum\limits_{j<i,r_j<r_i}f_j，答案为 \sum\limits_{j=1}\limits^nf_j。用树状数组维护，时间复杂度 O(n\log n)。

code。

例 9. Joisc2019_E 两道料理

题意描述：两道菜，分别有 n 和 m 个步数，每个步骤有需要的时间，一道菜的步骤必须按顺序进行，同一时间做多进行一个步骤，且必须进行，同时不能把一个步骤分开做，必须在一段时间内完成。两道菜的每个步骤有 t,e,c 表示这个步骤完成需要的时间 t ，且如果在 e 时刻前完成，获得 c 的分数，注意 c 可能为负数。1<n,m\leq 10^6。

可以通过二分把得分的条件可以转化成：在一道菜执行到 i 步骤时，另一道菜的步骤小于等于 p_i，则获得 c_i 的价值。

设 (x,y) 表示当前第一道菜完成 x 步，第二道菜完成 y 步的状态，依次连接所有状态构成一个阶梯形折线。总价值为第一道菜的 (i,p_i) 在折线下方的点和第二道菜的 (p_i,i) 在折线上方的点（都包括在折线上）的 c_i 之和。

用类似上面的思路可以想到 O(n^2) 的 DP：设 f_{i,j} 表示到达 (i,j) 的最大价值，它可能是从 (i-1,j) 和 (i,j-1) 转移到，最后加上与这个点纵坐标相同的点的贡献即可。

所以，这道题的数据结构需要在序列上维护以下操作：

可以运用上面例 3 的二分技巧维护，但也可以直接维护，主要思路是：全局取前缀最大值，相当于把有儿子的值与左儿子的最大值取最大值，所以可以维护前缀最大值标记和取最大值标记，且它们的优先级大于加标记的优先级。

code。

小结

这几道题目中都把一些数量用坐标的形式表现出来，可以发现阶梯这种性质来设置状态 DP 并优化。特别注意横坐标相同时，纵坐标的排序顺序。

Part 5. 线段树合并优化树上 DP（整体 DP）

树上 DP 的状态是 f_{u,i} 的形式，且节点 u 的有效状态数量是 O(size_u) 的，其中 size_u 表示子树的大小或者其它权值，满足 size_u=w_u+\sum\limits_{v=son(u)}size_v，size_{root}=O(n)，可以考虑用动态开点线段树记录状态，线段树合并进行转移，这时可能需要记录前后缀的信息，有时为了处理合并时一边空一边非空的情况，需要用懒标记。

例 10. 洛谷 P6773 [NOI2020] 命运

朴素解法

对于每个节点，求出最近的祖先要求它们路径之间有一条权值为 1 的边，记祖先的深度为 p_u。

考虑朴素的动态规划：f_{u,i} 表示满足这个条件的方案数：考虑节点 u 的子树，子树内没有满足条件的点中，最大的 p_v 为 i，即从它到它深度为 i 的祖先的路径上至少有一个权值为 1 的边；若不存在，i=0。

  1. 对节点 u，初始时，f_{u,p_u}=1，其它的值为 0。

  3. 然后去掉不合法的情况，即 \forall i\ge depth_u,f_{u,i}\gets0。

  4. 最后如果不是根节点，则可以让它到它父亲的边的权值设为 1，这样可以满足子树中的所有条件，即 f_{u,0}\gets f_{u,0}+\sum\limits_{i=0}^n f_{u,i}。

就是一个时间复杂度为 O(n^3) 的算法。另外可以用前缀和优化到 O(n^2)。

线段树合并

可以参考题目洛谷 P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并。

优化

容易发现，u 值不为 0 的状态必须在子树的 p_v 内出现过。

可以对每个节点用动态开点的线段树维护 f_u 和它的区间和。第一步、第三步、第四步中的操作是线段树的基本操作。

第二步，可以用合并实现，合并时记录 s_u,s_v 表示 u,v 两棵线段树中前面节点的 f 之和。分两种情况：

合并部分的参考代码：

inline int merge(int u, int v, LL f1, LL f2, int a = 0, int b = md)
{
    if(!u) return change(v, f1), v;
    if(!v) return change(u, f2), u;
    if(a == b)
    {
        t[u].f = (t[u].f * f2 + t[v].f * f1 + t[u].f * t[v].f) % P;
        return u;
    }
    int mid = a + b >> 1;
    pushdown(u), pushdown(v);
    t[u].r = merge(t[u].r, t[v].r, ADD(f1, t[t[u].l].f), ADD(f2, t[t[v].l].f), mid + 1, b);
    t[u].l = merge(t[u].l, t[v].l, f1, f2, a, mid);
    pushup(u);
    return u;
}

时间复杂度 O(n\log n)。

code。

例 11. 佳色出晴烟

题意描述：用 m 种不同颜色对 n 个节点的树涂色，要求相邻的两个点颜色不同，且格外 k 个要求 x_i,y_i 表示第 x_i 个节点不能染成颜色 y_i，求方案数对 998244353 取模。n\leq 2\times 10^5，m\leq 10^9，k\leq 4\times10^5。

考虑暴力 DP，设 f_{u,j}，表示 u 选颜色 j，u 的子树的答案，则所有 f 的初值为 1，每加入一个儿子 v，f_{u,i} 乘上 (\sum f_{v,j})-f_{v,i}，最后把所有 x_i=u 的 f_{u,y_i} 设为 0。

一个小优化是，只记录出现了限制的颜色的 f，其它节点的 f 值都是一样的，设这个值为 g_u，设子树 u 中出现限制的颜色数量为 s_u，则加入子树 v 时，g_u\gets g_u\left(\sum f_{v,j}+g_v(m-s_v-1)\right)，f_{u,i}\gets f_{u,i}\left(\left(\sum f_{v,j}\right)-f_{v,i}+g_v(m-s_v)\right)。

进一步优化，用动态开点线段树记录刚才的 f，依次进行以下操作：

时间复杂度 O(n\log n)。

code。

小结

用线段树合并优化状态是 f_{u,i} 的树上 DP，首先需要找到有效状态使得它们的数量是 O(size_u) 的，然后考虑子树合并时是否需要额外记录前后缀等信息，分别如何处理有相同叶子和一棵子树存在另一棵不存在的情况。

结语

线段树优化 DP 是一个比较有用的小技巧，不知道是哪次（2023）NOIP 考到了，本文用一些题目讲解了几种常见的套路，希望这篇文章可以帮助大家。