差分与区间更新（Java）

算法交互课 · JAVA · 从整段修改到两个端点

内部贡献不变，就只记录进入和退出时的变化。

先把边界定清，再用前缀扫描还原真实状态。每课均含完整步进、回退、播放、自定义输入、错误实验、Java 对照和三题自测。

学习入口

前置知识：数组、循环，以及前缀和的累计含义。这里从“查询区间”转向“修改区间”。

#	完整交互课	关键能力
01	区间加减：两个端点与一次还原	非零初值怎样构造差分？为何在 r+1 抵消？
02	拼车容量：半开行程与有序事件	同站上下车怎样合并？坐标十亿怎么办？
03	字母移位：累计正负影响再取模	为什么差分中可以有负数？Java 的负余数如何处理？

三种量不要混在一起

• 原数组 base[i]：修改前的值。
• 差分 diff[i]：从位置 i 起，累计值要改变多少。
• 还原值 active：走到 i 时，把之前的变化全部累加后的结果。

若 diff 是原值的相邻差，累计得到最终值；若 diff 只记录新增影响，累计后还需加回 base[i]。第一课采用前者，第三课用后者记录字母位移。

闭区间 [l,r] 在 l 进入、r+1 退出；半开区间 [start,end) 在 start 进入、end 退出。先明确题意，不能机械背一个 r+1。

进阶能力路线

三份材料包含九类套路。以下为后续学习导航，尚未实现这些进阶交互；通用框架不能替代每道题的适用条件与证明。

类别	下一步要学会的事情	自检问题
A 区间批处理	统一下标与边界，最后还原或校验	是否真的只需批量更新后的结果？
B 扫描线	在有序事件之间输出常值段	求覆盖长度时，有没有乘真实坐标差？
C 在线贪心 + 懒差分	先结算历史影响，再决定当前操作	为什么现在必须做？尾部无法再放窗口时是否真的无解？
D 二分答案 + 差分检查	证明单调性，每次 check 使用独立状态	多一个操作一定不会减少可行性吗？
E 覆盖次数 + 重排	先算位置频次，再把大值配大频次	题目是否允许任意重排？能否给出交换论证？
F 相邻变化构造	从零用区间 +1 构造非负目标时，只累计上升量	是否换成了可正可负的目标或 ±1 操作？若是，需重新推导
G 值域代价函数	对候选答案轴画分段代价并打标	每段代价与边界是否逐值核对？
H 环形区间	把跨界影响拆为两段线性区间	[l,n−1] 与 [0,r] 是否重复或遗漏？
I 多通道	同时维护计数、权重和等多种变化	是否对每条通道同步记录进入与退出？

Java 模板与工程边界

基础材料中的 DifferenceArray 提供 dirty 缓存：更新 O(1)，更新后首次单点查询触发 O(n) 还原，之后直到下次更新的单点查询 O(1)。snapshot() 即使缓存有效也要复制数组，仍是 O(n)。本课程把批量打标和统一还原显式拆开，方便观察。

连续更新再集中查询适合差分；每次更新后立即查询会反复扫描。动态需求需另选树状数组或线段树。long 降低 int 溢出风险，但并非无限大；生产输入仍须满足数值范围。

来源与整理说明

• S1《差分能力拆解分析.md》：A～I 分类、事件语义、边界、自检与练习路径。
• S2《差分能力拆解分析-白话版讲义.md》：技巧 1 的长度 6 样例、技巧 2 的有序事件、模板库与通俗推导。
• S3《差分-基础概念与模板驱动（Java）.md》：相邻差、n+1 哨兵、dirty 查询代价，以及 1109、1094、2381 的练习建议。

第一课沿用 S2 的 [1,3]+2; [2,5]+1 样例。拼车、移位的具体数据、固定错误实验与自测由本次教学设计补充，不当作原稿原句。原文件保持不变。

约定澄清： S2 部分示例分配 n+1，却仅在 r+1<n 时写退出点。因为输出不扫描 n，该写法也能得到相同的 n 项结果。本课统一写入 diff[n]，明确它是哨兵而非额外结果。若从非零 base 构造差分，diff[n] 初始为 0，不能据此宣称整条差分的总和恒为 0。

模板适用范围： S2 中仅返回 true 的 check 是待补的伪代码；固定从 i 开始补窗口的贪心，也不能直接当作任意“至少达到目标”问题的最优解。本次没有把这些代码作为可运行完整答案发布。