刚打完 LeetCode 第 484 场周赛趁热把 T4 复盘写下来。这一场的 T4 是典型的“优化型 DP”表面是区间划分真正的难点全集中在一个取模运算符上。如果你也经常在周赛 T4 上差一口气或者写出来的转移是 O(n^2) 然后被大数据量卡到超时这篇复盘应该能帮你把这类题的套路摸透。先交代一下背景。LeetCode 周赛固定四道题难度阶梯式上升前两题基本热手第三题开始上强度T4 才是真正的分水岭。484 场也不例外T4 卡住一大批人的点不是“没想到 DP”而是“想到了 DP 却优化不动”正好踩中竞赛里非常实用的一类技巧——用树状数组BIT把决策枚举变成区间最值查询。下面按我真实的做题顺序来写先还原题意再拆转移公式给完整代码最后是避坑清单和训练建议。第一次接触“数据结构优化 DP”的读者看完这篇再去找两三道同类题刷一遍基本就能自己上手了。1. 题目复盘还原 T4 的真面目1.1 题目大意与约束先把题意整理出来赛后按记忆还原大意如下给定长度为 n 的整数数组 nums 和一个正整数 k。可以将数组切成若干段连续子数组每段的得分定义为该段所有元素之和模 k 的结果。求所有切分方案中各段得分之和的最大值。约束1 ≤ n ≤ 10^51 ≤ k ≤ 10^50 ≤ nums[i] ≤ 10^9答案保证在 64 位整数范围内。我第一次读完这个题的反应是这不就是最经典的区间划分 DP 吗段和可以用前缀和 O(1) 拿然后 dp[i] max(dp[j] score(j1, i))五分钟就能写完。但再看一眼约束n 10^5O(n^2) 就是 10^10 次运算任何语言、任何常数都扛不住。所以这个题真正的考点不是“会不会 DP”而是“会不会把 DP 的决策过程优化到 O(n log n)”。1.2 为什么暴力的 O(n^2) 必死先把暴力写明白这是所有对拍的基础// O(n^2) 暴力只能过小数据用于对拍 vectorlong long dp(n 1, 0); for (int i 1; i n; i) { for (int j 0; j i; j) { long long seg ((pref[i] - pref[j]) % k k) % k; dp[i] max(dp[i], dp[j] seg); } }复杂度是 Σi n(n1)/2 ≈ 5×10^9 次内层计算每次还要做一次 64 位取模。取模本身在 CPU 上比加减乘贵不少实际跑下来轻轻松松几十秒评测机直接给你 TLE。暴力存在的唯一意义是等优化版本写完以后拿小数据对拍验证正确性。那优化的突破口在哪观察转移式dp[i] 依赖所有 j i我们不可能逐个枚举但能不能把“所有 j”按某种维度的最值一次性取出来这里的关键是先把 score(j1, i) 这个式子拆开拆成“只依赖 j 的部分”和“只依赖 i 的部分”。能拆开就有救。2. 转移公式拆解把取模变成两类加减2.1 用“模前缀和”表示区段得分设真实前缀和 S_i nums[1] ... nums[i]。段 [j1, i] 的和是 S_i - S_j得分是 (S_i - S_j) mod k。为了方便后续处理我们维护一个“模前缀和” p_i S_i mod k取值永远落在 [0, k-1]。这里有一个很多人会犹豫的点直接用模前缀相减再取模到底等不等于真实和的模答案是成立的因为模运算对加减是兼容的((a mod k) - (b mod k)) mod k (a - b) mod k。换句话说 p_i - p_j 和 S_i - S_j 只差 k 的整数倍取模结果完全一致。可以拿钟表来类比钟面上只有 k 个刻度从 p_j 这个时刻顺时针走到 p_i走的格数就是 (p_i - p_j) 的模结果。顺时针和逆时针是两条路这正好引出了下一节的分类讨论。2.2 分类讨论后的核心公式因为 p_i 和 p_j 都在 [0, k-1] 里差值只可能落在 (-(k-1), k-1)。所以对任意 j i当 p_j ≤ p_i 时(p_i - p_j) mod k p_i - p_j当 p_j p_i 时(p_i - p_j) mod k p_i - p_j k。把这两类分别代回 dp[i] max(dp[j] score(j1, i))就能把讨厌的取模符号完全消掉dp[i] max( p_i max_{ji, p_j ≤ p_i} (dp[j] - p_j), p_i k max_{ji, p_j p_i} (dp[j] - p_j) )注意到右边括号里的部分dp[j] - p_j只和 j 有关和 i 完全无关。于是我们只要维护一个“按 p_j 排序的集合”里面存的值是 v_j dp[j] - p_j然后对给定的阈值 p_i 分别做一次前缀最大值和一次后缀最大值查询。这就是整个题最核心的转化把“对每个 i 枚举所有 j”变成了“维护一个动态集合支持插入和前缀/后缀最值查询”。查询和插入分别做到 O(log n)总共 O(n log n)1e5 的数据量毫无压力。3. 树状数组优化数据结构接过枚举的活3.1 为什么是 BIT以及反向索引的技巧能维护前缀最值的数据结构不少线段树、树状数组、平衡树都能干。这里我选了树状数组理由很朴素——常数极小、代码短、好调试。树状数组原生只支持“单点更新 前缀查询”我们要的“后缀查询”可以通过下标翻转变成前缀查询。具体做法是坐标压缩把所有出现过的 p 值共 n1 个包含 p_0 0排序去重映射成 1..m 的 rank。然后开两个 BIT第一个 BIT 按原始 rank 存储query(r) 返回 rank ≤ r 的最大 v第二个 BIT 按下标翻转 rev m - rank 1 存储我们要查“rank r”的最大值等价于查 rev ≤ m - r 的区间也就是对第二个 BIT 做一次 query(m - r)。翻转索引的直觉是原来排在右边的元素翻转后被挤到左边。BIT 只会做前缀查询翻转一下就把后缀需求消化掉了。这里有个小细节必须写对第二类要的是严格大于所以查询下标是 m - r 而不是 m - r 1后者会把 rank r 的项也算进来导致公式错位。另一个容易踩的点是计算顺序。dp[i] 的合法转移 j 必须严格小于 i所以每一轮的正确顺序是先查询两个 BIT 得到当前的最优值、算出 dp[i]再把 (p_i, v_i) 插入两个 BIT供后面的 i 使用。如果先插后查dp[i] 就能拿到自己答案直接错掉。再补充一个进阶细节这里用的是最大值型 BIT它天然支持“只增不减”的插入操作。我们的场景里同一个 p 值可能出现多次每次只是往集合里新增一个 v树节点存的永远是历史所有插入里的最大值所以不会出现需要把某个节点调小的情况。如果哪天遇到需要删除或改小的场景BIT 就不够用了得换线段树。3.2 完整代码C17 / Python3C 版本#include bits/stdc.h using namespace std; using ll long long; const ll NEG -(1LL 60); struct BIT { int n; vectorll t; BIT(int n_ 0) : n(n_), t(n_ 1, NEG) {} void upd(int i, ll v) { for (; i n; i i -i) t[i] max(t[i], v); } ll qry(int i) { ll res NEG; for (; i 0; i - i -i) res max(res, t[i]); return res; } }; ll maxSegmentScore(const vectorll a, ll k) { int n (int)a.size() - 1; vectorll pref(n 1); for (int i 1; i n; i) pref[i] (pref[i - 1] a[i]) % k; vectorll coords pref; sort(coords.begin(), coords.end()); coords.erase(unique(coords.begin(), coords.end()), coords.end()); int m (int)coords.size(); auto id [](ll x) { return int(lower_bound(coords.begin(), coords.end(), x) - coords.begin()) 1; }; BIT le(m), gt(m); vectorll dp(n 1, 0); int r0 id(0); // p_0 0, dp[0] 0, v_0 0 le.upd(r0, 0); gt.upd(m - r0 1, 0); for (int i 1; i n; i) { int r id(pref[i]); ll best max(le.qry(r), gt.qry(m - r) k); dp[i] pref[i] best; ll v dp[i] - pref[i]; le.upd(r, v); gt.upd(m - r 1, v); } return dp[n]; }Python 版本from typing import List from bisect import bisect_left class BIT: def __init__(self, n): self.n n self.t [-10**30] * (n 1) def update(self, i, v): while i self.n: if v self.t[i]: self.t[i] v i i -i def query(self, i): res -10**30 while i 0: if self.t[i] res: res self.t[i] i - i -i return res class Solution: def maxScore(self, nums: List[int], k: int) - int: n len(nums) pref [0] * (n 1) for i, x in enumerate(nums, 1): pref[i] (pref[i - 1] x) % k coords sorted(set(pref)) m len(coords) def rank(x): return bisect_left(coords, x) 1 le, gt BIT(m), BIT(m) dp [0] * (n 1) r0 rank(0) le.update(r0, 0) gt.update(m - r0 1, 0) for i in range(1, n 1): r rank(pref[i]) best max(le.query(r), gt.query(m - r) k) dp[i] pref[i] best val dp[i] - pref[i] le.update(r, val) gt.update(m - r 1, val) return dp[n]两段代码逻辑完全一致核心就八行查 le、查 gt、合并、算 dp、算 v、插 le、插 gt、进入下一轮。3.3 复杂度与正确性验证时间上每轮两次查询加两次更新每次都是 O(log m)m ≤ n 1所以整体 O(n log n)。以 n 1e5 算大概几十万次 BIT 操作评测机毫秒级跑完。空间上pref、coords、dp 都是 O(n)两个 BIT 各 O(m)总数 O(n)。对比暴力的 O(n^2)这是一个数量级层面的碾压。方案状态数单次转移总复杂度n 1e5 时的量级暴力 DPnO(n) 枚举切分点O(n^2)约 5×10^9 次取模超时BIT 优化nO(log n) 查询 更新O(n log n)约 1.7×10^6 次 BIT 操作毫秒级正确性方面建议先拿几个手算例子验证。比如 nums [1,2,3], k 4完整一段得分 6 mod 4 2切 [1,2] [3] 得 3 3 6切 [1] [2] [3] 得 1 2 3 6最大值是 6和上面的算法输出一致。再比如 nums [5,5,5], k 7三段全切得分 5 5 5 15完整一段只有 1算法同样输出 15。我在比赛后还跑了随机小数据对拍暴力枚举所有切分和 BIT 版答案全对齐才算放心。4. 避坑清单这些错我一场比赛全踩过4.1 五个高频错误第一C 负数取模。如果手写 (p_i - p_j) % kp_j p_i 时会得到负数必须写成 ((x % k) k) % k。我这题采用分类讨论绕开了这个问题但如果你用的是另一种写法这个坑必踩。第二BIT 初始化不能用 0。v_j dp[j] - p_j 可能为负如果初值设成 0某些“其实没有合法选项”的位置会被当成选项选进去污染答案。要用一个足够小的 NEG比如 -(1LL 60)。第三严格大于和大于等于的区别。p_j p_i 时得分是 p_i - p_j 0属于第一类。所以第二类查询必须是 rank r反向 BIT 的下标是 m - r 而不是 m - r 1。写错的话小数据可能看不出来大点儿的样例直接答案偏大。第四忘插 j 0 的初始状态。dp[0] 0、p_0 0、v_0 0必须在循环开始前就放进两个 BIT否则“从第 1 个元素开始切一整段”这种划分根本不会被考虑。第五int 溢出。每段得分小于 k最多 n 段答案上限约 n×k 1e1032 位 int 装不下。所有 dp、pref、BIT 里的值一律 long long。症状原因修复出现负数结果C 对负数取模返回负统一 (x%kk)%k或按本文分类展开答案偏大、对拍全乱BIT 初值设 0无效状态被选中初始化为极小值如 -(1LL60)第二类分支混入 p_j p_i反向 BIT 查询下标多写了 1用 m - r保证严格大于漏掉从第 1 个元素开始的划分没插入 j 0 的初始状态循环前插入 p_0 0, v_0 0大样例答案异常甚至溢出int 存不下 n×k全部改用 long long4.2 对拍与自测小数据把坑讲完推荐一套自测流程。把第一节的暴力代码保留随机生成 n 不超过 12、k 不超过 20 的数组跑暴力版和 BIT 版逐项比对 dp 数组。一旦有差异立刻输出 i、p_i、两个 BIT 的查询结果一眼就能看出是哪个分支写歪了。这个方法在比赛里救过我无数次强烈建议平时练习就养成“顺便写个对拍”的习惯。小数据自测点我列几个全 0 数组所有 p 相同只走第一类k 1所有得分恒为 0答案应为 0nums 单调递增、p 单调递增p 出现大量重复值。每个边界过一遍基本能把 4.1 里的坑全部触发。5. 赛后复盘T4 到底在筛什么能力5.1 T4 的常见面孔复盘多了会发现周赛 T4 的套路其实是有限的。常见几类DP 加数据结构优化本场就是、树上启发式合并或换根 DP、图论最短路变体、字符串哈希与 KMP/AC 自动机变体。每一类背后都是几个基础模块的组合比如 leetcode 994 腐烂的橘子考的多源 BFS是图论里基础中的基础但它的思路经常被改造成周赛第三题基本计算器考的表达式解析和栈则是字符串类题的地基。T4 并不是每次都考冷门黑科技更多时候是把基础模块用更刁钻的方式组合起来。拿本场来说拆完公式后剩下的数据结构部分不过是“两个 BIT 坐标压缩”都是模板级操作。真正的分水岭在第二步你能不能想到把取模按大小关系拆成两类。这一步想通后面全是体力活。5.2 有针对性的训练路线如果你想稳定过 T4我的建议分三步走。第一步把 leetcode 热门 100 题里的动态规划、图、字符串题目做完确保基础模块不需要想。第二步专门练“转移化简”刷历史周赛的 T3/T4每道题先写暴力然后刻意问自己三个问题——枚举的维度能不能压缩、公式里有没有“只依赖 j 的部分”、哪些查询可以用 BIT/线段树/单调队列完成。第三步赛前把常用模板默写一遍BIT 最值、线段树区间最值、并查集、KMP、Dijkstra每个控制在三分钟内写完。比赛里的时间管理也很重要。T4 我一般先花五分钟把暴力写出来保底确认 dp 定义没理解错再考虑优化。真的卡住时暴力至少让你对题目有完整认识后面优化也只是在正确框架上做手术而不是推倒重来。6. 关于 “T4” 的另一个撞车含义6.1 NVIDIA T4 与 qwen3-vl-4b int4 并发写这篇复盘前搜资料时发现“T4” 在搜索里还有一个完全不同的语境NVIDIA 的 T4 显卡以及“T4 显卡跑 qwen3-vl-4b int4 能支持多少并发”这类问题。这里简单说明一下免得有人搜岔了。NVIDIA T4 是一块 16GB 显存的数据中心推理卡主打低功耗部署。qwen3-vl-4b 这类 4B 参数量模型做 int4 量化后权重大约 2~3GB单张 T4 理论上是放得下的但并发能力取决于很多因素输入输出长度、KV cache 大小、推理框架的动态批处理效率。粗略量级的话短文本场景下同时处理个位数到十几路请求是有可能的长上下文或高吞吐场景会明显下降。这个数字只能是参考真正要上线必须用 vLLM 这类框架做压测盯着显存和时延看。6.2 两种语境别搞混所以在 LeetCode 题解里搜“484 周赛 T4”T4 指第四道题在部署文档里搜“T4”指的是一块显卡。如果你是想找这场的解题思路顺着本文的公式和代码走就行如果你是在折腾模型推理那得去看显存规划和批处理策略完全是两个世界。搜索引擎把这两类词混在一起写这篇顺带提一嘴帮有需要的人避个弯。最后说点我自己的习惯。比赛里每次遇到这种“暴力公式摆在那、就是降不下来复杂度”的题我都会先逼自己把公式里的 mod、整除、绝对值这类非线性运算按取值区间拆成几个线性分支。拆开以后几乎都会发现剩下的东西就是“前缀最值 后缀最值”而这两个东西用树状数组或线段树十分钟就能写完。这个套路救过我很多次希望这篇复盘也能帮你在下次周赛 T4 上多拿下一题。