椰程信奥 · 说课稿

单文件互动课件 15 页 · 3 个模拟器 · 两道真题（BUCKET / INCDEC）

一、教材与学情

课题专题5 · 前缀和与差分（一）—— 数组的两次「降维打击」

课时1 课时（45 分钟）

对应真题USACO18DEC The Bucket List（水桶清单）、增减序列

学生在专题 1–4 已经能独立写模拟与枚举，但对「重复计算」的代价缺乏直觉：遇到多次区间求和，第一反应仍是for 循环。本讲要让他们第一次真切感到「换个存法，复杂度就降一个量级」。

知道

能准确说出前缀和的定义式与递推式、差分的两个改点，以及二者的互逆关系。

理解

能解释「为什么 b[r+1] -= x 而不是 b[r]」，以及「为什么区间和是 s[r]-s[l-1]」。

应用

能独立把「区间修改 + 最后查询」类问题翻译成「差分改 → 前缀和还原 → 取答案」三步流水线。

「先别急着记公式。我问一句：同一件事被问 10 万次，你还每次从头数一遍吗？」（第 2 页）

用这个反问切入，让学生先承认暴力写法会超时，再引出「把结果先存下来」。第 2 页并排放暴力与前缀和两段代码，复杂度差异用红色标出。

「s[i] 是前 i 项的和。那 [l,r] 的和怎么拿？——多算的部分减掉：s[r] 减掉 s[l-1]。」（第 3 页）

这里要让学生自己说出「减的是 l-1」，而不是我给。问错成 s[l] 时，用 a=[5,8,12,6] 查 [2,3] 当场算：s[3]-s[1]=25-5=20=8+12 ✓；若写成 s[3]-s[2]=25-13=12 ✗。一次就记住。

「差分只记『比前一个多多少』。前缀和查区间，差分改区间——记住各自的分工。」（第 4–5 页）

第 5 页的对照表是本讲骨架，务必让学生抄下来。随后第 6、7 页连开两个模拟器：先让学生猜结果，再点下一步验证。特别是差分模拟器，要让他们亲眼看 b[r+1] 那个位置变红。

「水桶清单：每头牛只改两个位置，最后扫一遍取最大。这就是那条流水线。」（第 8–9 页）

讲评时重点钉死 d[t+1] -= b。可以故意先写 d[t]，让学生用样例验算——他们会发现样例竟然也对（因为区间端点牛少），此时顺势讲清「样例通过 ≠ 写法正确」。

「增减序列：一次操作在差分上就是两个点的加减。全相等 ⇔ d₂…dₙ 全为 0。」（第 10–11 页）

本讲难点。用第 11 页的配对消元模拟器，让学生看着 P 与 Q 一个个被消掉，自己归纳出 max(P,Q)。结论不要先给，让他们从消元过程里数出来。

「最后 5 分钟，第 13 页那 5 条自检，写差分前默念一遍。」

前缀和：s[i]=s[i-1]+a[i]，s[0]=0　→　sum(l,r)=s[r]-s[l-1]

差分：b[i]=a[i]-a[i-1]　→　[l,r]+=x 只需 b[l]+=x, b[r+1]-=x

流水线：差分做修改 → 前缀和还原 → 取答案

增减序列：P=正数和 Q=|负数和|　→　次数=max(P,Q)　种数=|P-Q|+1

亮点一：两个模拟器把「不可见的中间数组」可视化。前缀和与差分的难点在于学生脑中构不出 s、b 数组长什么样。模拟器把每个下标的值都摊在表格里，理解成本大幅下降。

亮点二：用「样例通过但不通用」制造认知冲突。d[t] 与 d[t+1] 在小样例上可能都过，正是纠正「以样例论英雄」的最好时机。

可改进：增减序列的结论推导偏快，学困生可能跟不上。下次可增加一个「只有正数」或「只有负数」的退化样例，先建立单侧直觉。