前缀和与区间推理（Java）
你需要了解数组、下标和循环。学过枚举与状态维护会更容易理解后两节，但不是解锁条件。每课均有手动步进、回退、播放、自定义输入、错误实验、完整 Java 与三道自测。
| # | 完整交互课 | 这一课要解决的困惑 |
|---|---|---|
| 01 | 静态区间和：两个前缀相减 | 为什么多一格？为什么是 r+1？多次查询怎样复用？ |
| 02 | 和为 K 的子数组：查询历史前缀 | 为什么查 cur−K？空前缀是什么？为什么频次不能换成集合？ |
| 03 | 整除子数组：把同余前缀分组 | 为什么相同余数可以配对？Java 负余数怎么处理？ |
先统一坐标系
Section titled “先统一坐标系”P[t] 是前 t 个元素的和，覆盖原数组 [0,t)。 P[0]=0，P[i+1]=P[i]+nums[i]。
课程输入区间使用原数组闭区间 [l,r]，包含两端，所以和为 P[r+1]−P[l]。前缀位置 l 和 r+1 与原数组的左右端点不是同一组坐标。
freq[0]=1 表示空前缀出现过一次；firstSeen[0]=-1 则采用“上一个原数组元素位置”的另一套写法，不能把 -1 与前缀位置 0 随意混用。基础课统一画 P 的位置。
进阶路线：关系式相同，保存的信息不同
Section titled “进阶路线：关系式相同，保存的信息不同”以下是三份材料的进阶导航与学习提示，暂未制作交互课程。先写清题目要数量、长度还是最优值，再选择状态。
| 题面信号 | 应该维护什么 | 推理与边界 |
|---|---|---|
| 最长和为 K 的连续段 | firstSeen：目标前缀最早的位置 | 固定右端点，左前缀越早，长度越长；只记录首次出现 |
| 最短和为 K 的连续段 | lastSeen：目标前缀最近的位置 | 只在更早前缀中查询，再覆盖成当前位置；排除长度 0 |
| 0/1 或字母数字平衡 | 映射值，再查询相同前缀 | 把两类映射为 +1/−1，数量相等变成和为 0；数量不等式需另推条件 |
| 多段不重叠组合 | 左侧前缀最优结果 + 当前合法段 | 当前段 [l,r] 只能和完全位于 l 左侧的结果组合；最短总长度与最多段数不是同一目标 |
| 二维子矩阵计数 | 固定上下边界后的列和 | 每组行边界压成一维，再做“和为 K”计数；平均 O(R²C) |
| 距离和 / 绝对差代价 | 排好序的位置与它们的前缀和 | 对 x[i]，左代价为 i·x[i]−P[i]，右代价为 P[n]−P[i+1]−(n−i−1)·x[i] |
| 字符出现次数的奇偶性 | 异或 mask 的频次或首次位置 | 相同 mask 表示区间内各位奇偶抵消；允许一个奇数时还要查询相差一位的状态 |
| 不超过 K 的最大子数组和 | TreeSet 中有序的历史前缀 | cur−old≤K 推出 old≥cur−K，用 ceiling 找到最小满足者；无候选时要明确无解 |
距离公式依赖位置有序；乘法先转 long。含负数的区间和不一定随窗口扩大而增加，不能无条件套滑动窗口。只有能相减并恢复区间信息的累计量适合直接做前缀差，区间最小值不满足这个性质。
与动态结构的选择
Section titled “与动态结构的选择”静态数组、多次求和适合前缀和：构建 O(n)，每次查询 O(1)。修改一个元素会影响其后的所有前缀，不能把静态查询优势理解为更新也便宜。频繁修改可考虑树状数组或线段树；本专题不实现动态容器、在线判题或任意代码执行。
来源与核对记录
Section titled “来源与核对记录”- S1《前缀和-解题能力逆向工程.md》：实战分类、两个前缀的关系、哨兵、容器语义与边界检查。
- S2《前缀和-解题能力逆向工程-白话版.md》：前置知识、技巧 1～3 的样例与推导、后续技巧的路线导航。
- S3《前缀和-数据结构基础模板（Java）.md》：§1～3 前缀定义与静态 NumArray、§5 边界错误、§6 练习路径、§7 结构选择。
交互限制、固定错误实验和自测为本次教学设计。保留原稿，课程中的整理与校对不伪称原文原句。
教学修订： S2 技巧 6 的矩阵 [[1,0],[0,1]]、target=1，按三组行边界压缩分别得到 2、2、2 段，总计 6，不是原文的 1、2、1 与总计 4。每组行边界维护列和与一维哈希扫描均为 O(C)，总体平均 O(R²C)，不再额外乘一次 C。该进阶动画尚未制作。
复杂度适用范围： 仅构造前缀数组，不会让所有子数组问题自动变成 O(n)。如果仍枚举每个左右边界，候选数量仍是 O(n²)；后两课还需要关系变形与历史频次查询。