从一道题，到一份可复用的题解

01 / 先把问题说清楚

考虑一个很小的问题：给定长度为 n 的数组，多次询问闭区间 [l, r] 内所有元素的和。数组不会在查询之间改变，且每次查询都满足 1 ≤ l ≤ r ≤ n。

最直接的办法是每次遍历这个区间。单次查询最多访问 n 个元素，q 次查询的最坏时间复杂度为 O(nq)。写下这个基线，才能说明后面的优化究竟省掉了什么。

题解开头不必重抄整段题面，但应留下三个要点：输入代表什么、需要输出什么、哪些约束决定算法能否使用。尤其是“数组不变”这个条件，它决定了预处理得到的结果能被反复使用。

相邻区间的求和包含大量重复计算。定义前缀和 S[i] 为前 i 个元素的和，并设 S[0] = 0，就有：

S[i] = S[i - 1] + a[i]
sum(l, r) = S[r] - S[l - 1]

原因是 S[r] 已包含第 1 到第 r 个元素，而 S[l − 1] 恰好包含区间之前的部分。相减之后，只留下第 l 到第 r 个元素。这个解释比“套用前缀和”多一步，却能说明公式的正确性。

例如数组为 [2, 1, 3, 4, 2]，前缀和是 [0, 2, 3, 6, 10, 12]。查询 [2, 4] 时，结果为 S[4] − S[1] = 10 − 2 = 8，与 1 + 3 + 4 一致。

预处理只遍历一次数组，时间复杂度 O(n)，每次查询 O(1)，总时间复杂度 O(n + q)，额外空间 O(n)。数组若会修改，就需要重新考虑这份预处理是否仍然有效。

实现之前，列出能够揭露下标错误的输入：单个元素、查询整个数组、l = 1、l = r、出现负数。它们能检查 S[0] 的初始化，也能检查“闭区间”有没有被误写成别的范围。

整数类型也来自约束。如果每个数的绝对值不超过 A，那么任意前缀和的绝对值最多为 nA。应按这个上界选择类型；使用更宽的整数类型，也要确认它能够容纳可能的和。

一份可复用的题解，可以按“模型 → 基线 → 观察 → 正确性 → 复杂度 → 边界”的顺序组织。

最后记录卡住自己的那一步：是没有看到重复计算，还是区间下标写错了？下一次复习时，真正值得再做的往往就是这一小段，而不是已经熟悉的代码。