Fixed Sum · 增量更新

窗口和：出一个、进一个，不必重算

先从最基础的一类问题入门：窗口宽度固定为 k，从左滑到右，每个位置求窗内的和（或均值）。窗口右移一格，其实只滑走最左边一个、滑进最右边一个，中间 $k-2$ 个数原封不动——所以新窗口的和 = 旧窗口的和 $-$ 出去的 + 进来的，一次加减就更新完，不必把 k 个数重加一遍。这个「增量更新」是滑动窗口的核心，把朴素的 $O(n\cdot k)$ 压到 $O(n)$ 。

1 · 增量，省在哪

朴素法每个窗口把 k 个数从头加一遍，总加法 $\approx (n-k+1)\cdot k$ ；增量法只在第一个窗口加 k 次，之后每滑一格只做「一减一加」两次，总共 $k + 2(n-k)$ 次，与 k 无关地落在 $O(n)$ 。窗口越宽、数组越长，差距越显著。

增量更新的前提：窗口聚合值可增量维护——和、计数、含某字符个数都可以，因为「出 / 进」对结果的影响是可加可减的。但最大值不满足这一条件：滑走的那个若恰是当前最大，新的最大值无法靠一次减法算出来（得在剩下 $k-1$ 个里重新找）。这个问题由窗内取最值一页展开，并在双端单调队列得到 $O(n)$ 的解法。