专题 21 前缀和·差分·双指针 · 复习强化

考点：前缀和的定义（A1）。

（A1）考点：前缀和的定义——pre[i] 是前 i 项之和。

解析：本题考查前缀和的定义。pre[i] = a[1] + ... + a[i] 把「从头加到 i」预先算好存表，之后任何区间的和都能由两个前缀相减得到。它是「以空间换时间」最基础的形态。

排除法：A 以为是第 i 项自身的人把「和表」当成了「原表」；B 以为是后 i 项之和的人方向反了，那是后缀和；C 以为是相邻两项之差的人描述的是差分数组。

考点：下标从 1 起的好处（A2）。

（A2）考点：下标从 1 起的好处——pre[0]=0 哨兵统一公式。

解析：本题考查下标从 1 起的好处。pre[0] = 0 让「前 $i$ 项和」与「区间 $[1,i]$ 的和」合二为一：递推第一步 pre[1] = pre[0] + a[1] 无特判，查询 $[1,r]$ 时 pre[r] - pre[0] 公式照用。

排除法：D 以为更快的人把编码便利错当性能；C 以为省内存的人多开一位反而多花内存；A 以为题目强制的人没理解这是工程选择。

考点：pre 的递推式（A3）。

（A3）考点：pre 的递推式——pre[i] = pre[i-1] + a[i]。

解析：本题考查 pre 的递推式。每步只做一次加法：前面的和已经躺在 pre[i-1] 里，加上新元素即得 pre[i]。整表一趟 $O(n)$ 建成。

排除法：B 写减法的人把差分构造混了进来；D 写 a[i-1] + a[i] 的人丢掉了历史的积累；A 写 pre[i+1] 的人引用了还没算出的未来值。

考点：区间和公式（A4）。

（A4）考点：区间和公式——pre[r] - pre[l-1]。

解析：本题考查区间和公式。闭区间 $[l,r]$ 的和 = 前 $r$ 项和减去前 $l{-}1$ 项和。减 $l{-}1$ 而不是 $l$，是因为第 $l$ 项本身属于区间要保留。

排除法：D 减 pre[l] 的人把第 $l$ 项也减掉了；A 减 pre[r-1] 的人得到的是单元素 $a[r]$；B 相加的人把两个前缀堆在一起毫无意义。

考点：公式中减法的含义（A5）。

（A5）考点：公式中减法的含义——削掉区间外的前段。

解析：本题考查公式中减法的含义。pre[r] 是 $[1,r]$ 的和，多算了 $[1,l-1]$ 这一段；减去 pre[l-1] 恰好削掉这段，剩下 $[l,r]$。一加一减是「集合差」思想的直译。

排除法：D 以为互为相反数的人没看两个前缀都是正表；C 以为 pre 是差分数组的人概念串台；B 以为减法消除负数的人无中生有。

考点：预处理的复杂度（A6）。

（A6）考点：预处理的复杂度——一趟递推 O(n)。

解析：本题考查预处理的复杂度。$n$ 个元素、每步一次加法，建表总代价 $O(n)$。相比暴力每次查询 $O(n)$，一次预处理后每次查询只要 $O(1)$。

排除法：A 答 $O(n^2)$ 的人以为要双重循环；B 答 $O(n\log_2 n)$ 的人把排序的量级错安过来；C 答 $O(1)$ 的人忘了建表本身要走一遍。

考点：前缀和数组的长度（A7）。

（A7）考点：前缀和数组的长度——开 n+1 位。

解析：本题考查前缀和数组的长度。下标 $0$（哨兵）到 $n$（全和）共 $n{+}1$ 位。开 $n$ 位会越界写 pre[n]（P5 展开）。

排除法：C 开 $n$ 位的人忘了哨兵与末位；D 开 $2n$ 位的人浪费一倍；B 开 $n-1$ 位的人两头都缺。

考点：与逐项累加的对比（A8）。

（A8）考点：与逐项累加的对比——查询多时前缀和碾压。

解析：本题考查与逐项累加的对比。单次查询两者都能做；$m$ 次查询时逐项法 $O(nm)$、前缀和法 $O(n+m)$——预处理成本一次付清后查询全是 $O(1)$。

排除法：D 以为前缀和永远更慢的人没算查询摊销；C 以为逐项永远更快的人没见过百万次查询；A 以为完全等价的人忽略了规模差异。

考点：区间求和模板（B1）。

（B1）考点：区间求和模板——建表、读 l r、查表三步。

解析：本题考查区间求和模板。标准流水线：一趟建 pre，每次询问读入 $l, r$，输出 pre[r] - pre[l-1]。模板短小但每一环都是考点（A3、A4）。

排除法：B 每次循环累加的人放弃了预处理；A 先排序的人破坏了区间的原始结构；C 建树查询的人（线段树）超出入门范围。

考点：多次查询的收益（B2）。

（B2）考点：多次查询的收益——总复杂度 O(n+m)。

解析：本题考查多次查询的收益。$m$ 次查询的总代价 = 预处理 $O(n)$ + 查询 $m \times O(1)$ = $O(n+m)$；暴力则是 $O(n \times m)$。$m$ 越大差距越悬殊。

排除法：A 答 $O(n \times m)$ 的人描述的是暴力；B 答 $O(m\log_2 m)$ 的人把排序量级错安；D 答 $O(n^2)$ 的人双重循环想多了。

考点：前缀和求前 k 平均（B3）。

（B3）考点：前缀和求前 k 平均——pre[k] / k。

解析：本题考查前缀和求前 k 平均。前 $k$ 项的和就在 pre[k]，除以项数 $k$ 即得平均。分母不是 $k{+}1$（哨兵不占项数），也不必动 pre[k-1]。

排除法：D 除以 $k+1$ 的人把哨兵位当成了数据；C 用 pre[k-1] 的人少算一项；A 用 a[k] 的人只取了末元素。

考点：前缀和法最大子段（B4）。

（B4）考点：前缀和法最大子段——pre[j] 减历史最小前缀。

解析：本题考查前缀和法最大子段。以 $j$ 结尾的最大子段 = pre[j] - min(pre[0..j-1])：减去最小的历史前缀，剩下的区间和最大。扫描时维护「至今最小前缀」即可，与 17 卷的 DP 法殊途同归。

排除法：B 拿 pre[j] 本身的人算的是从头到 $j$ 的整段；C 拿相邻差的人只得了单元素；D 拿 max 减 min 的人忽视了「最小必须出现在最大之前」的次序约束。

考点：前缀和相等的含义（B5）。

（B5）考点：前缀和相等的含义——中间段和为零。

解析：本题考查前缀和相等的含义。pre[i] == pre[j] 说明从 $i{+}1$ 到 $j$ 加起来净变化为零——这段子段的和为 $0$。这是「数和为零子段」类问题的钥匙（N2 实测）。

排除法：C 以为元素全相等的人把和为零与值相等混淆；D 以为全数组为零的人以偏概全；A 以为 i 与 j 相同的人没理解 $i < j$ 的前提。

考点：前缀和计数统计（B6）。

（B6）考点：前缀和计数统计——数对 (i,j) 满足 pre[j]-pre[i]=k。

解析：本题考查前缀和计数统计。「子段和恰为 $k$」翻成前缀和语言：找 pre[j] - pre[i] == k 的对数；对每个 $j$ 要数历史中值为 pre[j] - k 的前缀个数。有序/哈希加速属提高视野，初赛懂转化即可。

排除法：A 认为只能暴力枚举的人没做前缀和转化；D 数原数组中值为 $k$ 的元素的人混淆了「元素」与「子段和」；C 排序数相邻差的人是另一道题的做法。

考点：差分的定义（C1）。

（C1）考点：差分的定义——d[i] = a[i] - a[i-1]。

解析：本题考查差分的定义。差分记录「相邻两项的变化量」：约定 d[1] = a[1]（起点从 $0$ 跳到 $a[1]$），其后每格存增量。它是前缀和的逆操作（C2）。

排除法：C 写相加的人把方向弄反；D 写前 $i$ 项和的人描述的是前缀和；B 写 a[i+1] - a[i] 的人错位一格且漏了首项。

考点：差分与前缀和互逆（C2）。

（C2）考点：差分与前缀和互逆——差分求前缀和还原原数组。

解析：本题考查差分与前缀和互逆。原数组取差分得 $d$，对 $d$ 取前缀和又回到原数组；两个操作互为逆变换。「差分是记录变化，前缀和是重演变化」。

排除法：A 以为互不相干的人没发现互逆关系；C 以为两倍关系的人臆造数量关系；B 说前缀和是差分特例且方向相同的人——两者方向恰好相反，一拆一合。

考点：区间加的两端打点（C3）。

（C3）考点：区间加的两端打点——d[l]+=v、d[r+1]-=v。

解析：本题考查区间加的两端打点。区间 $[l,r]$ 整体加 $v$ 在「变化量」视角下只有两个事件：位置 $l$ 处开始多出 $v$、位置 $r{+}1$ 处 $v$ 停止。$O(1)$ 两笔代替 $O(r-l)$ 逐格改。

排除法：B 区间内逐格改 $d$ 的人把差分当成了原数组；D 只打 d[l] 的人让 $v$ 一直泄漏到结尾（P2）；A 减点打 $r$ 的人让区间右端少加一次（C6）。

考点：差分的还原（C4）。

（C4）考点：差分的还原——求一遍前缀和。

解析：本题考查差分的还原。打点结束后差分数组只记「变化的坡度」，要得到真实值需前缀和把坡度累回去：b[i] = b[i-1] + d[i]。一次 $O(n)$。

排除法：D 再求一遍差分的人原地转圈（得到二阶差分）；B 排序的人破坏位置语义；C 直接输出 $d$ 的人输出了变化量不是值。

考点：单点值的来历（C5）。

（C5）考点：单点值的来历——累加所有起点不晚于 i 的打点。

解析：本题考查单点值的来历。b[i] = d[1] + ... + d[i]：凡 $l \le i$ 的加法都在累加列里，而 $r{+}1 \le i$ 的减法恰好把过期的影响抵消——区间效果由「先加后减」自动雕刻出来。

排除法：B 以为只与 d[i] 有关的人没理解累加链；C 以为差分等于原数组的人忘了还原步骤；D 以为累加顺序影响结果的人——加法交换律保证无关。

考点：右端减点的位置（C6）。

（C6）考点：右端减点的位置——减点打在 r+1。

解析：本题考查右端减点的位置。位置 $r$ 还在区间内必须吃到 $v$，累加到 $r$ 时不能被减；到 $r{+}1$ 才该停止，所以减点打 $r{+}1$。打 $r$ 会让区间右端漏加、打 $r{+}2$ 会多加一格。

排除法：B 认为打 $r$ 一样的人会在边界题上翻车；A 认为为了数组变长的人因果倒置；C 认为 $r{+}2$ 也可以的人多泄漏一格。

考点：多次区间加的叠加（C7）。

（C7）考点：多次区间加的叠加——打点互相叠加一次还原。

解析：本题考查多次区间加的叠加。每个操作只打两个点，多个操作的点在同一差分数组上自然累加；最后一次前缀和统一还原——$m$ 个操作总代价 $O(m)$ 加一次 $O(n)$。

排除法：B 每操作立即还原的人白白付出 $m$ 次 $O(n)$；A 以为越叠越接近暴力的人没算打点的 $O(1)$；C 以为不能叠加的人没试过多点共存。

考点：区间加模板（D1）。

（D1）考点：区间加模板——零差分起步、打点、还原。

解析：本题考查区间加模板。全零差分数组起步（初值就是「无变化」），每个操作 d[l]+=v; d[r+1]-=v;，最后前缀和输出。若原数组非零，可先把它当第一个「操作」打进去或建完差分再叠加。

排除法：A 每操作立即改原数组的人退化成暴力；D 先建前缀和再打点的人把两张表的角色弄混；B 逐位置枚举操作的人 $O(nm)$。

考点：离线批量区间操作（D2）。

（D2）考点：离线批量区间操作——攒齐后统一计算。

解析：本题考查离线批量区间操作。差分天然离线：操作攒着打点、最后统一还原，不要求「边到边答」。与之相对的在线要逐个响应（提高级视野），初赛知道这对概念即可（大纲未明列，解析关联）。

排除法：C 选在线处理的人含义恰好相反；D 选随机化的人无中生有；A 选分治的人把另一种范式错安。

考点：染色计数问题（D3）。

（D3）考点：染色计数问题——差分适合可加量、覆盖语义需另配手段。

解析：本题考查染色计数问题。差分擅长「可加可减」的量（次数、总量）；「后涂覆盖先涂」的覆盖语义不满足可加性，纯差分不够——可按时间序处理或转成「每位置最后一次操作是谁」的问题再配差分统计边界。辨清量纲再选工具。

排除法：C 认为差分完全不能碰的人过于绝对（统计边界事件仍可用）；A 以为颜色就是差分数组的人维度混乱；D 以为涂色次数即答案的人没考虑覆盖。

考点：区间加后整体输出（D4）。

（D4）考点：区间加后整体输出——总复杂度 O(n+m)。

解析：本题考查区间加后整体输出。$m$ 次打点 $O(m)$ + 一次还原 $O(n)$，总 $O(n+m)$；暴力 $m$ 次逐格改是 $O(n \times m)$。这就是差分在「多次区间修改、最后一次查询」场景的完整收益。

排除法：C 答 $O(n \times m)$ 的人描述的是暴力；B 答 $O(m\log_2 n)$ 的人给数据结构（线段树）的量级错安；A 答 $O(n^2)$ 的人双重循环想多了。

考点：差分数组的构造（D5）。

（D5）考点：差分数组的构造——d[1]=a[1]，其后相邻作差。

解析：本题考查差分数组的构造。从零数组跳到 $a[1]$ 的变化量就是 $a[1]$ 本身，故 d[1]=a[1]；其后 d[i] = a[i] - a[i-1]。构造后即可在其上继续打区间操作。

排除法：A 原样照抄的人没做差分；D 用 a[i+1]-a[i] 的人错位且漏末项；B 用相邻相加的人方向全反。

考点：区间减的处理（D6）。

（D6）考点：区间减的处理——两端打点方向相反。

解析：本题考查区间减的处理。减 $v$ 就是加 $-v$：d[l] -= v; d[r+1] += v;——与区间加恰好镜像。加减混合时各自打点、差分自动净额结算。

排除法：C 认为无法表示的人忘了负数；D 写与加相同的人把方向弄反；B 先取相反数组的人多绕一圈。

考点：区间加与单点查综合（D7）。

（D7）考点：区间加与单点查综合——只查一点可 O(m) 直接累计。

解析：本题考查区间加与单点查综合。位置 $p$ 的终值 = 所有满足 $l \le p$ 且 $r \ge p$ 的操作的 $v$ 之和——遍历 $m$ 个操作累计即可，$O(m)$ 且无需还原整个数组（J3、N3 同型）。

排除法：D 必须整体还原的人没发现单点查询可以只看相关操作；B 认为无法计算的人低估了区间包含判断；A 每操作立即更新 $p$ 的人虽对但每次 $O(1)$ 累计才是其更简形式。

考点：容斥加法公式（E1）。

（E1）考点：容斥加法公式——减去 s[i-1][j-1] 防重复。

解析：本题考查容斥加法公式。s[i-1][j]（上方矩形）与 s[i][j-1]（左侧矩形）的并集把左上角 s[i-1][j-1] 算了两遍，减一遍才是真并——这正是容斥「加两次减一次」。

排除法：B 以为左上角不属于任何子阵的人没画重叠区；C 以为让结果更小的人没理解这是去重不是打折；A 以为修越界的人把它当成了边界补丁。

考点：二维递推式（E2）。

（E2）考点：二维递推式——s[i][j] 是左上角到 (i,j) 的矩形和。

解析：本题考查二维递推式。s[i][j] 定义为以 $(1,1)$、$(i,j)$ 为对角的矩形内全部元素之和；递推时新格 $(i,j)$ 的值 = 上矩形 + 左矩形 − 重叠 + 自身。整表 $O(nm)$ 建成。

排除法：D 以为是第 i 行和或第 j 列和的人把二维压成了一维；C 以为是对角线和的人维度错乱；B 以为与单行无关的人——单行恰是二维表的特例一列退化。

考点：子阵和容斥减法（E3）。

（E3）考点：子阵和容斥减法——大矩形减两条多算的边再加回角。

解析：本题考查子阵和容斥减法。以大矩形 s[x2][y2] 为底，减去目标上方（s[x1-1][y2]）与左侧（s[x2][y1-1]）多算的两块，但左上角被减了两次要加回 s[x1-1][y1-1]——一减一减一加，与递推容斥同源。

排除法：A 只减 s[x1][y1] 的人既错位又漏加回；C 相加的人方向全反；B 拿 s[x2][y2] 本身的人算的是整个大矩形。

考点：全阵和的特例（E4）。

（E4）考点：全阵和的特例——s[n][m] 直接就是。

解析：本题考查全阵和的特例。全阵即「从 $(1,1)$ 到 $(n,m)$」的最大子阵，前缀和表右下角 s[n][m] 就是答案——查表公式里两个被减项都是第 0 行列（零），加回项也是零，天然退化。

排除法：C 减 s[n-1][m-1] 的人把最后一行一列丢了；A 重新逐格累加的人放弃了查表；B 所有行相减的人无中生有。

考点：边界行列的来源（E5）。

（E5）考点：边界行列的来源——第 0 行列全零免特判。

解析：本题考查边界行列的来源。s[0][j] 与 s[i][0] 全为 $0$（空矩形无元素），使 $i=1$ 或 $j=1$ 时递推与查表公式照常成立——二维版的一维哨兵推广。

排除法：C 以为存原始数据的人把表当成了矩阵本身；D 以为表示无穷的人方向反了；A 以为可省略的人会在边界上写一堆特判。

考点：二维应用场景（E6）。

（E6）考点：二维应用场景——矩阵上多次矩形区域和查询。

解析：本题考查二维应用场景。棋盘格权、图像亮度、地图海拔——凡是「多次询问某矩形区域总和」都归二维前缀和管。预处理 $O(nm)$ 后每次查询 $O(1)$。

排除法：B 链表翻转是序列结构操作；C 树路径查询需树上前缀（提高级）；D 字符串匹配归 KMP（提高级）。

考点：对撞指针的定义（F1）。

（F1）考点：对撞指针的定义——两端相向而行。

解析：本题考查对撞指针的定义。l 从最左、r 从最右，每步依据当前条件让一边向中间收拢；两指针相遇即终止。有序数组找数对是它的招牌场景（G1）。

排除法：D 同向同速的人描述的是快慢指针雏形；C 都向左移动的人右指针方向反了；B 随机选位置的人放弃了确定性。

考点：同向快慢指针（F2）。

（F2）考点：同向快慢指针——一前一后都向右。

解析：本题考查同向快慢指针。慢指针标记「已确认/保留段」的边界，快指针逐个探新元素；两指针之间的空隙天然承载「待处理/待淘汰」的语义。原地去重（L3）是标准应用。

排除法：C 一左一右的人是对撞；B 同速不动的人没有遍历；A 找环的那种「快慢」是链表特定语境（16 卷 G 组），此处指同向双标。

考点：滑动窗口的定义（F3）。

（F3）考点：滑动窗口的定义——双指针维护的连续区间。

解析：本题考查滑动窗口的定义。窗口 [l, r] 是同向双指针夹出的连续段：右端扩张吃进新元素、左端收缩吐出旧元素，像一扇在数组上滑动的窗。窗口和的 $O(1)$ 增量更新是它的核心技巧（G4）。

排除法：D 以为窗口固定不动的人忘了「滑动」；B 以为是排序算法的人名字联想错误；A 以为是二分的人把另一种 $O(\log)$ 技巧错安。

考点：双指针的 O(n) 本质（F4）。

（F4）考点：双指针的 O(n) 本质——两指针单向移动合计至多 2n 步。

解析：本题考查双指针的 O(n) 本质。正确性靠单调性兜底、效率靠「不回退」保证：每个指针从进到出只朝一个方向走，总步数上界 $2n$。若有回退，就不再是这个量级。

排除法：D 只答嵌套一层的人没指出不回退这个关键；A 以为靠有序的人——有序是正确性前提之一但不是效率来源本身；C 以为数据范围小的人无中生有。

考点：双指针的前提（F5）。

（F5）考点：双指针的前提——单调性保证移动方向唯一。

解析：本题考查双指针的前提。有序数组里「固定一端、和随另一端移动单调变化」，指针每步能确定地淘汰一批候选——单调性断了（无序乱跳）双指针就失去依据。

排除法：C 要求元素互不相同的人加了不存在的前提；B 要求偶数长度的人无中生有；A 以为任何数组都行的人没见过无序数组上双指针漏解的反例。

考点：与暴力对比（F6）。

（F6）考点：与暴力对比——每步淘汰一批候选。

解析：本题考查与暴力对比。暴力 $O(n^2)$ 枚举所有数对；对撞双指针每步比较后能淘汰「以当前 l 为左端的所有更大 r」或「以当前 r 为右端的所有更小 l」中的一批——$n$ 步内出结果。

排除法：B 以为都是 $O(n^2)$ 的人没算淘汰的规模；D 以为 $O(\log_2 n)$ 的人把它与二分混淆；A 以为暴力更快的人违背量级常识。

考点：指针的移动规则（F7）。

（F7）考点：指针的移动规则——和偏小移左端。

解析：本题考查指针的移动规则。当前和偏小说明「左边的数不够大」：有序数组里增大和的唯一途径是左指针右移（右指针已在最大候选侧）。偏大则对称地右指针左移。

排除法：B 移右指针的人会让和更小越走越远；D 双移的人一步跨过多个候选可能错过解；C 重置的人放弃了已获信息。

考点：有序两数之和（G1）。

（G1）考点：有序两数之和——首尾对撞先中 1+11。

解析：本题考查有序两数之和。{1,3,5,7,9,11} 找和 $12$：首尾 $1{+}11{=}12$ 第一步即中（L1 实测）。即使首步不中，每步淘汰也向解收敛。

排除法：A 答 $(5,7)$ 的人给的是合法解但不是双指针首先找到的；D 答 $(3,9)$ 的人同样晚于首步命中；C 答 $(1,3)$ 的人两数之和根本不等于目标。

考点：有序去重（G2）。

（G2）考点：有序去重——相邻比较即可。

解析：本题考查有序去重。排序让相等值聚成相邻段，「新值出现」当且仅当 a[i] != a[i-1]——一次扫描计数即可（L2 实测 $3$ 个不同值）。无序数组则需哈希等手段（提高级视野）。

排除法：A 必须哈希的人忘了有序前提已把问题变简单；B 统计数组长度的人把重复也算了；C 对每个值再搜一遍的人 $O(n^2)$。

考点：窗口最长子段（G3）。

（G3）考点：窗口最长子段——右进左缩取最长。

解析：本题考查窗口最长子段。右端每进一个元素，若窗口和超限就从左端收缩到合法，用 r - l + 1 更新最长——右进左缩各不回退，$O(n)$（L4 实测长度 $3$）。

排除法：A 枚举所有子段的人 $O(n^2)$；C 先排序的人破坏连续性；D 从中间向两边扩的人把回文子串的思路错安。

考点：窗口和统计（G4）。

（G4）考点：窗口和统计——进一个出一个 O(1) 更新。

解析：本题考查窗口和统计。窗长 $k$ 的窗从左滑到右：sum += a[r] 的同时 sum -= a[r-k]（滑出窗口的那个），每窗和 $O(1)$ 更新（N5 实测 7 16 35 36 27）。

排除法：B 每窗从头累加的人 $O(nk)$；A 把 sum 覆盖成单元素的人丢了窗口内容；D 加上滑出元素的人方向反了。

考点：对撞找满足条件（G5）。

（G5）考点：对撞找满足条件——固定一端满足条件的是一段前缀。

解析：本题考查对撞找满足条件。固定 $r$ 时满足 a[l]+a[r] <= s 的 $l$ 是一段连续前缀；$r$ 向左移时这段前缀的边界只向右单调收缩——两指针各扫一遍完成统计。这是「数不超过条件的对」的标准论证。

排除法：C 以为无序也可以的人丢了单调前提；B 以为条件与数值无关的人架空了排序；D 以为对数不超过两个的人没见过批量统计。

考点：双序列合并（G6）。

（G6）考点：双序列合并——各指一头取较小者。

解析：本题考查双序列合并。两个有序序列各一个指针指头部，每步取较小者入结果并推进该指针；一方耗尽后把另一方整体接上——归并排序的合并步正是它（08 卷关联）。

排除法：D 拼接再排序的人 $O((n{+}m)\log)$ 且丢了线性合并的意义；A 随机交替的人破坏有序性；C 嵌套两两比较的人 $O(n \times m)$。

考点：相邻间隔双指针（G7）。

（G7）考点：相邻间隔双指针——一次遍历求最大间隔。

解析：本题考查相邻间隔双指针。有序数组相邻差的最大值一次扫描即得：维护 a[i+1] - a[i] 的最大者——「间隔为 1 的同向双指针」最简形态。

排除法：D 两两枚举所有对的人把 $O(n)$ 做成 $O(n^2)$；A 二分查找间隔的人没有搜索目标；B 排序后递归的人多此一举。

考点：前缀和与差分的配合（H1）。

（H1）考点：前缀和与差分的配合——差分管写、前缀和管读。

解析：本题考查前缀和与差分的配合。多次区间修改用差分打点（写的优化）、多次区间查询用前缀和查表（读的优化）；两者同源于「前缀和互逆」结构，常配合出场（修改完差分还原成新数组再建前缀和）。

排除法：D 不能同时用的人没见过「先改后查」两段式；C 必须排序的人给两者强加了无关前提；B 说反角色的人恰好互换。

考点：窗口与前缀和组合（H2）。

（H2）考点：窗口与前缀和组合——固定窗和的两种等价写法。

解析：本题考查窗口与前缀和组合。固定窗长 $k$ 的各窗和：逐窗加减维护省一个数组、pre[r] - pre[r-k] 查表更通用（任意 $l,r$ 即查即得）；两者同为 $O(n)$，按题意取用（N5、O3 对比）。

排除法：D 以为前缀和必然超时的人量级算错；B 以为逐窗必错的人冤枉了维护法；C 以为不能混用的人过度保守。

考点：离线处理思想（H3）。

（H3）考点：离线处理思想——攒齐操作统一计算。

解析：本题考查离线处理思想。差分批量打点正是离线思想的化身：不急着还原、攒完所有操作一次性算。与在线（逐个响应）相对（大纲未明列、上机通用，解析关联）。

排除法：B 选在线处理的人语义恰好相反——在线是逐个响应；A 选贪心的人把策略范式错安到时机概念；D 选动态规划的人同样答非所问。

考点：复杂度对比选择（H4）。

（H4）考点：复杂度对比选择——排序根本不解决区间和。

解析：本题考查复杂度对比选择。逐项 $O(nm)$、前缀和 $O(n+m)$；排序会打乱元素原始位置、破坏区间结构，对区间和问题既慢又错——先问「问题要什么」再选工具。

排除法：B 以为三者同为 $O(nm)$ 的人低估了前缀和；D 以为排序最快的人南辕北辙；C 以为逐项 $O(1)$ 的人忘了循环。

考点：场景与技术匹配（H5）。

（H5）考点：场景与技术匹配——反复区间加减净量问差分。

解析：本题考查场景与技术匹配。浇水加、蒸发减、最后问净水量：正负区间操作叠加正是差分的画像——每次操作 $O(1)$ 打点、末尾一次还原。

排除法：B 对撞指针的人答非所问（没有两端收缩结构）；D 滑动窗口的人没有窗口约束语义；A 排序去重的人丢掉了量纲。

考点：综合判断（H6）。

（H6）考点：综合判断——三者同以「预处理/单调性换重复计算」为魂。

解析：本题考查综合判断。前缀和用一张表换掉重复累加、差分用两端打点换掉逐格修改、双指针用单调淘汰换掉重复枚举——三者的共同灵魂是「花一次便宜的成本，省掉重复的贵成本」。

排除法：D 都必须有序的人——只有双指针部分场景要有序，前缀和差分与序无关；B 差分不能处理负增量的人忘了负数即减；A 前缀和只适用正数的人——负数前缀照样定义良好。

考点：pre 递推输出（I1）。

（I1）考点：pre 递推输出——{3,1,4,1,5} 的 pre 为 3 4 8 9 14。

解析：本题考查 pre 递推输出。逐位累加：$3$、$3{+}1{=}4$、$4{+}4{=}8$、$8{+}1{=}9$、$9{+}5{=}14$，输出 3 4 8 9 14。递推只看前一位，追踪到 $5$ 步即得。

排除法：A 照抄原数的人没做累加；D 多打一个 $14$ 的人多循环了一轮；C 从 $0$ 打头的人把哨兵也输出了。

考点：区间和查表（I2）。

（I2）考点：区间和查表——pre[4]-pre[1]=6。

解析：本题考查区间和查表。区间 $[2,4]$ 即元素 $1,4,1$，和为 $6$：pre[4] - pre[1] = 9 - 3。查表两减法 $O(1)$。

排除法：D 答 $5$ 的人少算了一项；B 答 $11$ 的人把减法做成了 pre[4]+pre[1]；A 答 $8$ 的人查的是 $[1,3]$。

考点：多次查询（I3）。

（I3）考点：多次查询——[1,3] 得 8、[3,5] 得 10。

解析：本题考查多次查询。$[1,3]$：pre[3]-pre[0]=8（$3{+}1{+}4$）；$[3,5]$：pre[5]-pre[2]=10（$4{+}1{+}5$）。两次查询各自 $O(1)$，前缀和的摊销优势正在此。

排除法：A 答 $8$ 与 $8$ 的人第二问算成了 $[1,3]$；B 答 $3$ 与 $10$ 的人第一问只取了单元素；D 答 $14$ 与 $14$ 的人两次都给了全和。

考点：pre 自身最大（I4）。

（I4）考点：pre 自身最大——{-2,3,-1} 的 pre 为 {0,-2,1,0}。

解析：本题考查 pre 自身最大。含哨兵 pre[0]=0 的完整前缀表为 {0, -2, 1, 0}；负数前缀是判断「和为零子段」（B5）的基础数据。

排除法：B 漏哨兵的人少一位；C 漏末位的人少了最后的回零；D 符号反了的人差分构造混入。

考点：区间和作差（I5）。

（I5）考点：区间和作差——pre[5]-pre[2] 对应 [3,5] 得 10。

解析：本题考查区间和作差。减 pre[2] 削掉前两项，剩 $[3,5]$ 的 $4{+}1{+}5{=}10$。公式与区间的翻译是查表题的基本功。

排除法：C 答区间 $[2,5]$ 与 $11$ 的人少减了一项的界限；A 答 $[3,5]$ 但值 $9$ 的人算错一位；B 答 $[4,5]$ 与 $6$ 的人多减了一项。

考点：前缀和模板补全（I6）。

（I6）考点：前缀和模板补全——pre[i-1] + a[i]。

解析：本题考查前缀和模板补全。递推铁三角：前缀、新元素、加号。填 pre[i+1] 引用未来值未定义；填 a[i-1]+a[i] 丢了历史；减号是差分构造。

排除法：A 引用未来的人顺序没懂；D 丢历史的人把累加当成了局部和；C 减号的人方向全反。

考点：两端打点还原（J1）。

（J1）考点：两端打点还原——[2,4] 加 3 得 0 3 3 3 0。

解析：本题考查两端打点还原。d[2]+=3, d[5]-=3 后前缀和：位置 $1$ 吃不到加（$0$）、位置 $2..4$ 各吃到 $3$、位置 $5$ 加减抵消（$0$）——区间形状被两端雕刻出来。

排除法：C 末位也是 $3$ 的人忘了位置 $5$ 的减点生效；D 全 $3$ 的人把打点当成了全加；B 错位一格的人两端位置都偏。

考点：两次区间加（J2）。

（J2）考点：两次区间加——[1,3]+2 与 [3,5]+5 得 2 2 7 5 5 0。

解析：本题考查两次区间加。位置 $1,2$ 只吃 $2$；位置 $3$ 同吃 $2$ 与 $5$ 得 $7$；位置 $4,5$ 只吃 $5$；位置 $6$ 两个减点都在、净 $0$。叠加净额在还原时自动结算。

排除法：D 末位 $5$ 的人漏了 $[3,5]$ 的减点在 $6$；A 位置 $3$ 得 $5$ 的人忘了叠加；B 全 $7$ 的人区间边界全错。

考点：区间加后单点查（J3）。

（J3）考点：区间加后单点查——位置 3 得 7、位置 5 得 0。

解析：本题考查区间加后单点查。$[2,4]$ 加 $7$：位置 $3$ 在区间内得 $7$；位置 $5$ 在区间外得 $0$。单点判断「$l \le p \le r$」即得，无需还原全表（D7）。

排除法：C 答位置 $5$ 也是 $7$ 的人区间右界弄错；A 答 $0$ 与 $7$ 对调的人包含判断反了；B 答 $14$ 的人把打点值 $7$ 加了两遍。

考点：差分数组构造（J4）。

（J4）考点：差分数组构造——{5,5,8} 的 d 为 5 0 3。

解析：本题考查差分数组构造。d[1]=a[1]=5（从 $0$ 跳到 $5$）；$d[2]=5-5=0$（无变化）；$d[3]=8-5=3$（增 $3$）。构造完即可验证：前缀和 $5,5,8$ 复原。

排除法：D 照抄原数的人没做差分；B $5,-3,3$ 的人第二项减反；C $0,0,3$ 的人漏了首项跳变。

考点：差分还原模板（J5）。

（J5）考点：差分还原模板——b[i-1] + d[i]。

解析：本题考查差分还原模板。还原即对 $d$ 求前缀和：b[i] = b[i-1] + d[i]、b[0]=0。减号方向是「再差分」不是还原。

排除法：D 引用 b[i+1] 的人顺序反了；A 直接拿 d[i] 的人输出的是变化量；C 减号的人越还原越错。

考点：区间减执行（J6）。

（J6）考点：区间减执行——[1,3]+2 与 [2,2]-2 得 2 0 2 0。

解析：本题考查区间减执行。位置 $1$ 只吃 $+2$ 得 $2$；位置 $2$ 吃 $+2$ 与 $-2$ 净 $0$；位置 $3$ 只吃 $+2$ 得 $2$；位置 $4$ 无影响 $0$。减的打点是 d[2]-=2; d[3]+=2。

排除法：B 位置 $2$ 得 $2$ 的人减点没生效；A 位置 $4$ 得 $2$ 的人减点位置错；C 全 $2$ 的人把减当没发生。

考点：递推终点值（K1）。

（K1）考点：递推终点值——s[3][3] = 45。

解析：本题考查递推终点值。$3\times3$ 全阵和 $1{+}\cdots{+}9=45$ 正是 s[3][3]——递推到右下角覆盖全阵（E4）。

排除法：B 答 $15$ 的人只算了一行；D 答 $9$ 的人只取了右下角格；C 答 $24$ 的人容斥符号错。

考点：子阵和查表（K2）。

（K2）考点：子阵和查表——子阵 {5,6,8,9} 和 28。

解析：本题考查子阵和查表。45 - 6(第一行) - 12(第一列) + 1(左上角) $= 28$——容斥三步一气呵成，区域恰为 $\{5,6,8,9\}$。

排除法：A 答 $45$ 的人没做排除；D 答 $26$ 的人加回项算错；B 答 $11$ 的人只算了 $2$ 与 $9$ 对角。

考点：容斥中间值（K3）。

（K3）考点：容斥中间值——s[1][3]=6、s[3][1]=12。

解析：本题考查容斥中间值。s[1][3] 是第一行 $1{+}2{+}3{=}6$；s[3][1] 是第一列 $1{+}4{+}7{=}12$。这两个被减项正是查表公式的两块「多算」。

排除法：B 答 $12$ 与 $6$ 对调的人行列不分；D 全答 $6$ 的人漏了第一列的 $12$；C 答 $3$ 与 $7$ 的人只取了单格。

考点：左上子阵和（K4）。

（K4）考点：左上子阵和——s[2][2] = 12。

解析：本题考查左上子阵和。左上 $2\times2$ 区域 $\{1,2,4,5\}$ 和为 $12$：递推中间值也是查表可能项——前缀表的每一格都是一块矩形的答案。

排除法：C 答 $10$ 的人漏加 $2$；B 答 $14$ 的人多算了 $6$；A 答 $6$ 的人只算了第一行。

考点：全阵和（K5）。

（K5）考点：全阵和——s[3][3] = 45。

解析：本题考查全阵和。查表公式取 $(1,1)$ 到 $(3,3)$：被减两项落第 $0$ 行列（零）、加回项亦零，答案就是 s[3][3] $=45$——全阵是子阵的特例。

排除法：A 减 s[2][2] 得 $33$ 的人丢了末行末列；C 两块相加得 $42$ 的人重复扣减；B 答 $36$ 的人矩阵元素看错。

考点：二维模板补全（K6）。

（K6）考点：二维模板补全——减 s[i-1][j-1]。

解析：本题考查二维模板补全。递推的四个加数：上块、左块、负的左上块、新元素。减 s[i-1][j-1] 是容斥去重；其它选项都破坏代数恒等。

排除法：A 加回未来块的人越界；C 填自身的人自引用；D 减元素值的人量纲错位。

考点：对撞找数对（L1）。

（L1）考点：对撞找数对——首步 1+11 命中。

解析：本题考查对撞找数对。$l$ 指 $1$、$r$ 指 $11$：和恰 $12$ 立即输出 1,11 并 break（G1 的代码形态）。若首步不中则按偏小偏大移针。