1. 从一道题说开去：为什么“序列划分”值得单独写一篇
先说个我自己的经历。前阵子带一个算法训练小组，有个学员拿了一道很基础的题目来问，大意是给一个数组，要求把它划分成若干连续段，使得每一段满足某种数学性质，然后求方案数或者最值。他第一反应是套DP，第二反应是套贪心，但怎么都过不了样例。我看了一眼题面，发现这题的考点根本不是“怎么划分”，而是“什么样的划分是合法的”。这就是序列划分类题目最大的坑：你以为你在处理选择，其实你在处理约束。
“序列划分”这四个字，严格来说不是一个独立的知识点，而是一类问题的统称。它常用于指代：给定一个长度为n的序列，要求将其切割成若干连续段，每个子段需要满足某些条件（比如和相等、最大值不超过某值、按位与相同等），在此基础上求划分方案数、最小段数、最大权值等目标。这类题在各大平台里出现频率极高，从div2的B题到div1的压轴都有可能，但核心思想是共通的。
这篇内容主要面向三类读者：一是刚入门、刷题量在100~300之间、被“划分题”卡过几次的选手；二是准备面试、需要快速掌握常见套路的人；三是纯粹对数学推导感兴趣的读者。我会从最基础的数学建模开始，逐步拆解几类经典划分问题，讲清楚每一步推导背后的动机，而不只是甩结论。
2. 先建模：把“划分”翻译成数学语言
2.1 为什么要先建模
很多初学者拿到序列划分题的第一反应是：“这不就是个搜索吗？”如果n很小，确实可以dfs枚举所有切割点，复杂度O(2^n)，但n一旦到了1e5级别，这条路直接堵死。所以我们需要做的第一件事，是把“划分”这个动作翻译成一个能用数学工具处理的模型。
先说最经典的建模方式。假设我们要把长度为n的数组a划分成k段，分割点记为p1, p2, ..., p_{k-1}，那么每一段可以表示为：
- 第1段：a[1..p1]
- 第2段：a[p1+1..p2]
- ...
- 第k段：a[p_{k-1}+1..n]
如果目标是最小化某个代价函数f，比如各段最大值之和、各段和的最大值，那么问题就变成一个分段决策问题。这类问题有一个天然适合的工具：动态规划。
2.2 前缀和与区间的数学表达
在几乎所有的序列划分题目里，都需要快速计算任意区间[l, r]的某种统计量。最基础的就是区间和，这要用到前缀和：
设pre[i]表示a[1]到a[i]的和，那么区间[l, r]的和就是pre[r] - pre[l-1]。
不要小看这一步。很多题目里，区间和的表达式会直接决定整个DP的复杂度。比如“把数组分成若干段，使得每一段的和都相等”这类题，如果段数很多，你没法枚举每个分割点，就必须利用前缀和的性质快速判断“某个位置是否可以作为段边界”。
再往外延伸一步，有的题要求的是区间异或、区间按位与、区间最大值等，这些虽然有各自的“快速查询”方式（如ST表、线段树、前缀线性基等），但在“划分”这个语境下，它们的核心作用都一样：把子段条件变成一个可比较的表达式，从而缩小可行分割点的范围。
我在实际做题时经常发现，把题目里的“每一段满足条件X”写成一个数学命题，再观察这个命题有没有“单调性”或“结合律”，是解题最关键的一步。这一步做对了，后面就是套模板；做不对，就会越算越乱。
2.3 第一类经典模型：前缀和相等划分
先看一道入门级但非常经典的题目：
给定长度为n的数组a，要求把数组划分成尽可能多的连续段，使得每一段的和相等。
这个题面短，但暗含了一个很重要的逻辑：因为所有段的和相等，设为S，那么整体数组的总和total必须等于k * S。也就是说，S必须是total的约数，并且段数k = total / S。
一种朴素的思路是枚举S，然后扫一遍数组，看看能否正好切出若干段和为S。复杂度是O(n * div(total))，div(total)是total的约数个数。这在total较小时没问题，但当数组元素很大，total的约数很多时，就有点悬了。
更优的做法是：注意到如果最后一段的右端点是n，那么倒数第二段分割后的和也必须是S。利用前缀和，我们可以发现每个合法的段边界位置i，必然满足pre[i]是S的倍数。记cnt[x]表示前缀和等于x的位置个数，那么对于给定的S，合法的段数就是能凑出的“前缀和为S、2S、3S...”的链条长度。
换句话说，这个问题可以转化为：构建一个从前缀和x到x+S的转移图，求从0出发的最长链。这一步转化把“划分数数组”变成了“在一堆前缀和里跳步”，数学结构一下子清晰了。
如果在赛场上碰到类似的题，我会先写一个暴力枚举S的版本，把样例和随机小数据都过了，再去看是否值得优化。因为这种题往往不是为了卡复杂度而卡复杂度，而是考察“你能否发现前缀和的倍数关系”。
3. 常见序列划分题型与核心推导思路
3.1 最小化“最大值”：二分答案 + 贪心判定
有一类题长这样：把数组分成m段，要求每段和的最大值最小。这是典型的“二分答案贪心判定”模型。
为什么要用二分？因为“最大值最小”这种最优化问题，直接DP的话状态是O(n*m)，在n=1e5、m=1e5时不可行。但如果把问题反过来问：给定一个上界cap，能不能用不超过m段完成划分？这是一个可以贪心判断的问题——遍历数组，每段累加，一旦超过cap就开新段。判断复杂度O(n)，配合二分答案，总复杂度O(n * log(sum))。
这里分享一个我踩过的坑：二分边界设置。下界通常是max(a[i])，因为任何一段的和都不可能小于单个元素的最大值；上界通常是sum(a)。有些新手会把下界设成1或0，会导致二分过程中出现“段和永远不可能满足”的假象，然后莫名TLE。不是复杂度的问题，而是判定函数里开了太多不必要的新段。
下面是一个简洁的判定函数示例（伪代码风格）：
bool check(long long cap, int m) { long long cur = 0; int seg = 1; for (int i = 1; i <= n; i++) { if (a[i] > cap) return false; if (cur + a[i] > cap) { seg++; cur = a[i]; } else { cur += a[i]; } } return seg <= m; }不要以为这个模板背下来就完事了。关键是要理解为什么贪心是成立的：当给定cap时，每一段都尽可能塞满，才能让段数最少。反过来，如果“尽可能塞满”都满足不了段数上限，那其他分配方式更不可能满足。这个“贪心最优性”的证明，才是面试官想听到的。
3.2 划分方案计数与DP优化
计数类划分题是另一个大分支。最常见的是：求把数组划分成k段，且每段满足某性质，方案总数是多少。
直接定义状态dp[i][j]表示前i个元素划分成j段的方案数，转移时枚举最后一段的起点。如果暴力转移，复杂度O(n^2 * k)，很明显需要优化。优化方向通常有两个：
第一个方向是利用前缀和加速转移。假设合法段的末尾满足pre[i] - pre[l-1] 在某个范围，那么dp[i][j] = sum(dp[l-1][j-1])，这个求和可以用前缀和数组在O(1)完成，前提是l的取值范围是连续的。很多题里l的范围可以通过二分（如区间和要求不超过某个值）或单调指针（如区间最大值不超过某值）快速确定。
第二个方向是利用同余关系分组。比如当段的条件是“区间异或值为某个定值”时，dp[i]可能只与前缀异或值相同的状态有关，这时可以用哈希表维护每个“状态类别”的和，做到O(n log n)。
我有一次做CF的一道划分计数题，卡在了“区间和取模相等”这个条件上。暴力转移O(n^2)，后来发现条件等价于pre[i] ≡ pre[l-1] (mod K)，于是可以用一个cnt数组记录每种模数出现的“DP和”，转移时直接取对应的值。这个技巧我后来在至少三道题里都用到了，算是性价比极高的一类优化。
3.3 维护“段性质”的数据结构：单调栈与单调队列
还有一类题，段的合法性取决于段内最大/最小值与段长的关系。例如：把数组划分成若干段，每段的长度不超过其最小值。这种题的难点在于“合法段”的判断不是简单的前缀和，而是需要动态维护区间最小值。
我常用的做法是单调栈 + DP优化。以“每段的长度不超过其最小值”为例，设dp[i]表示前i个元素的划分方案数，转移时需要知道最近的“能作为当前段最小值”的位置。维护一个单调递增栈，当新元素入栈时，栈内某些元素的“管辖范围”会变化，相应地维护一个关于dp转移的累加值。
这里有个细节需要注意：单调栈里存的不是位置就是值，取决于题目需要。但无论是哪种，核心是利用“单调性”把“哪些位置可以作为最后一段的起点”压缩成一个连续的区间，再用某种数据结构（线段树、树状数组或懒标记）快速取和。
4. 实操：手把手拆解一道综合型序列划分题
4.1 题目原型回顾
假设我们有这样一道题：
给定长度为n的正整数数组a，要求将其划分为若干个连续段，使得每一段的和与段内最大值的差不超过K。求最小段数。
n ≤ 2e5，a[i] ≤ 1e9，K ≤ 1e9。
这题把“最小化段数”和“段内约束”结合了起来。乍一看像二分答案贪心，但由于“每一段的和与最大值的差”不是单调的——段越长，和会增加，但最大值也可能变，所以直接贪心可能会选错。
4.2 我的推导过程
第一步，考虑DP。设dp[i]表示前i个元素的最小段数。转移是：
dp[i] = min(dp[j-1] + 1)，其中j是满足sum(a[j..i]) - max(a[j..i]) ≤ K的最远左端点。
问题变成：对于每个i，快速求出最小的合法j。这里有两个量：区间和和区间最大值。随着j变小（区间变长），sum会变大，但max也有变化，所以“合法j”的范围并不是一个单纯的区间。
我的处理方式是这样的：枚举i，同时维护一个“可能成为区间最大值”的候选集合。利用单调栈，每次加入a[i]时，会把栈内一些较小的元素弹出，弹出时它们的贡献会合并。这个合并过程正好对应着“这些元素作为最大值时，左端点j的范围”。
具体来说，线段树每个位置j维护的是“以j为左端点时，当前区间(j..i)的sum - max”。当加入a[i]时，区间和整体增加a[i]，也就是对线段树上所有j做区间加；而max的变化则需要把某些连续段的“max值”从旧值改成a[i]。使用单调栈可以确定“哪些位置j的max需要更新”，每次更新是一个区间覆盖操作。
维护好线段树后，对于当前i，我只需要找到最小的j，使得val[j] ≤ K，然后dp[i] = dp[j-1] + 1。为了快速找这个j，线段树可以额外维护“val超过K的最小下标”，或者再套一个二分。
4.3 代码骨架与关键细节
下面给一个核心代码骨架，重点是线段树维护和单调栈更新的配合：
struct Node { long long minVal; // 当前左端点j的 sum - max 的最小值 long long lazy; // 区间加标记 long long mnVal; // 真正的最小值 }; // 单调栈：栈内维护元素值递增（或索引） vector<int> stk; for (int i = 1; i <= n; i++) { // 1. 区间和：所有左端点j <= i，区间(j..i)的和都增加了a[i] seg.rangeAdd(1, i, a[i]); // 2. 维护最大值的贡献 int last = i; while (!stk.empty() && a[stk.back()] <= a[i]) { // 对于左端点j在(stk[secondLast] + 1 .. stk[back])的区间， // 旧max是a[stk[back]]，新max变成a[i] int cur = stk.back(); stk.pop_back(); int l = stk.empty() ? 1 : stk.back() + 1; // 区间(l..cur)的max值从a[cur]提升到a[i] seg.rangeChange(l, cur, a[i] - a[cur]); // 这里实现时用lazy标记维护相对增量 } stk.push_back(i); // 3. 在线段树上找最小的合法j int pos = seg.search(K); // 返回最小的j，使得val[j] <= K dp[i] = dp[pos - 1] + 1; }这里有三个地方特别容易写错：
第一，rangeChange和rangeAdd必须分开处理，不能混用同一个lazy标记。因为“区间和增加”是整体加上一个数，而“max替换”是把区间内一些位置的val整体调整为某个新值，这两者虽然都可以用区间操作表示，但意义不同。我因为把二者合并成同一个lazy，错了一次，调试了两小时。
第二，单调栈的弹出条件必须是<=而不是<。如果遇到相等值，用<=可以把相等元素的贡献合并，避免重复计算，否则可能漏掉某些左端点的更新。
第三，seg.search(K)的实现：我们希望找到最左边的位置j，满足val[j] ≤ K。如果线段树维护的是最小值，可以这样做：从根节点开始，先看左子树的最小值是否≤K，是就往左走，否则往右走。这样一次查询是O(log n)，整体复杂度O(n log n)。
4.4 复杂度分析
每个元素最多入栈出栈各一次，所以单调栈是O(n)。线段树每次操作（区间加、区间改、单点查询/搜索）都是O(log n)，总共O(n log n)。在n=2e5时，一秒内跑完毫无压力。
对比一下暴力方案：枚举左端点j，再用数据结构维护区间最值，整体O(n^2)显然不可行。这个例子说明了“单调栈+线段树”这个组合在序列划分题里的实用性——它能把看似“区间选择”的问题，转化成一个“动态维护左端点集合”的问题，复杂度直接降一个量级。
5. 常见问题与调试心得
5.1 边界条件出错
序列划分题最常见的问题就是边界。我总结出几个高频出错点：
- 前缀和数组下标从1开始还是从0开始。很多人喜欢把pre[0]=0，但DP状态转移时，如果dp[0]表示“空序列的划分”，那么所有涉及“从0开始划分”的转移都要单独处理。
- 二分答案时下界取max(a[i])，上界取sum(a)。面试时如果题目说a[i]可以是正数或负数，下界和上界的取法完全不同，需要重新分析单调性。
- 当k段数可能为0时（如允许不划分），dp初值要设置成INF还是0，必须先想清楚。
5.2 贪心失效的场景
我见过不少同学一看到“最小段数”“最大划分”，就下意识写贪心：能塞就塞。但贪心是否成立，取决于“局部最优是否能推出全局最优”。前面提到的“sum - max ≤ K”这个题，如果直接用“段和超过限制就开新段”的贪心，在一些数据上会得到错误的段数。
我曾经构造过一个反例：
a = [5, 1, 5], K = 4如果贪心从左往右，第一段塞5（sum=5, max=5, diff=0），第二段塞1（sum=6, max=5, diff=1），第三段塞5（sum=11, max=5, diff=6>4），被迫开新段，总共3段。但如果第一段只选[5]，第二段选[1,5]，分段是2段，明显更优。原因在于：让第一段包含更多元素，反而挤占了后续段的“容量”。这说明这类题不能简单贪心，必须DP。
5.3 线段树 lazy 标记的坑
线段树维护区间加、区间改时，lazy标记的优先级容易写乱。我的习惯是：在pushdown时，先处理区间改，再处理区间加。因为区间改相当于把整个区间的值赋为同一个值，这时候之前的加的lazy应该被清空；而区间加是在已经改过的基础上再加，所以顺序不能反。
如果你用的是结构体节点，一定要在 applyChange 时把加标记清零，否则后续区间加会叠加上去，导致结果错误。这属于“编译不报错，但答案全错”的经典问题，只能靠跟踪小样例定位。
6. 工具与练习建议
6.1 题目练习清单
如果想把序列划分练扎实，我建议按这个顺序刷题：
- 入门：给定数组，求是否存在一种划分使得每段和都等于K（经典前缀和+哈希）。
- 基础：把数组分成m段，求每段和最大值的最小值（二分答案+贪心）。
- 提高：求划分成若干段使得每段按位与为0的最大段数（拆位贪心）。
- 进阶：划分后每段的和与最大值的差不超过K，求最小段数（单调栈+线段树）。
- 竞赛向：计数类划分，且段合法性取模同余（前缀和+分组）。
刷题时不要只看题解，我建议每道题都用手推一遍样例，再用随机小数据暴力对拍。对拍是检验算法正确性的最好办法——写一个O(2^n)或O(n^2)的暴力，和你的优化算法跑随机数据，如果输出不一致，就缩小数据范围定位。
6.2 代码模板沉淀
做多了以后，你会发现这类题的代码结构很固定。我自己会维护一个模板库，包含以下几类：
- 前缀和/差分模板。
- 二分判定模板（带有上下界、合法性检查）。
- 单调栈模板（支持区间最大值更新）。
- 线段树模板（支持区间加、区间覆盖、区间最小值查询、搜索）。
模板不是死背，而是为了减少重复劳动。真正做题时，把模板调出来，根据题目条件修改“合法段判断”的函数，就能快速进入状态。
7. 从题目到思维：序列划分能力的迁移价值
训练序列划分类的题目，表面上是在学“怎么切数组”，本质是在练一种“约束下的决策能力”。尤其是“单调栈+线段树维护左端点集合”这类组合思路，在其他算法里也有很强的迁移性：
- 滑动窗口类问题中，要动态维护窗口内的最大值和最小值，同时判断窗口是否合法。
- 动态规划优化中的“决策单调性”，很多也可以理解为维护一个合法的决策左边界。
- 字符串的切分问题（如把字符串划分成若干回文子串的最小次数），本质上也是序列划分的变体。
- 树上的链划分、图上的连通块划分，也经常用到类似的“前缀信息+约束判断”思维。
我自己带人的时候常说：做题不要盯着题号，要盯着题的“骨架”。序列划分题骨架就是“枚举右端点 + 维护合法左端点集合 + 用结构快速取转移值”。骨架懂了，蒙上题号你也能认出来。
最后分享一个排错的小技巧：在调试DP转移时，把每一步的“合法左端点区间”打印出来，看它是否连续，是否符合预期。很多时候算法挂掉不是转移公式错，而是合法区间维护错了。打印区间是定位最快的办法。每次遇到这类题，我都是先用暴力跑通小数据，再逐步替换优化部分，最后再做复杂度测试。养成这个习惯之后，写序列划分题的出错率会明显下降。
