前缀和解决什么问题
想象你有一排书架，每层放不同数量的书。朋友频繁问你：从第 l 层到第 r 层一共有多少本书？如果每次你都重新数一遍，效率很低。前缀和就是提前算好“从第1层到每一层累计的书数”，这样每次回答只需一次减法，不用重复数。
前缀和专门解决频繁区间求和问题——给定一个数组，多次询问某个子数组的和。它用空间换时间，预处理后每次查询只需 O(1) 时间。
前缀和数组怎么构建
假设原数组为 arr，长度为 n。我们构建一个长度 n+1 的前缀和数组 pre，其中 pre[0] = 0，然后依次计算：pre[i] = pre[i-1] + arr[i-1]（i 从 1 到 n）。
这样 pre[i] 就表示原数组前 i 个元素的和。例如 pre[3] 是 arr[0] + arr[1] + arr[2]。构建过程只需遍历一次数组，时间复杂度 O(n)。
区间和公式 pre[r]-pre[l-1]
要计算原数组从下标 l 到 r（包含）的区间和，直接用公式：区间和 = pre[r+1] - pre[l]（如果 pre 长度是 n+1 且 pre[0]=0）。
为什么？因为 pre[r+1] 是前 r+1 个元素的和（即下标 0 到 r），pre[l] 是前 l 个元素的和（下标 0 到 l-1），相减正好剩下下标 l 到 r 的和。这个公式让每次查询只需 O(1) 时间。
复杂度对比：暴力 vs 前缀和
| 方法 | 预处理时间 | 单次查询时间 | 空间 |
|---|---|---|---|
| 暴力 | O(1) | O(n) | O(1) |
| 前缀和 | O(n) | O(1) | O(n) |
暴力法每次查询都要遍历区间，当查询次数 m 很大时，总时间 O(m·n) 会非常慢。前缀和虽然多花一点空间和预处理时间，但每次查询瞬间完成，适合查询次数多的场景。
延伸：差分与二维前缀和
差分是前缀和的逆运算：给定原数组，差分数组记录相邻元素的差值。差分擅长频繁区间更新（如给某段统一加一个数），然后通过一次前缀和还原原数组。
二维前缀和把一维思想扩展到矩阵。构建时：pre[i][j] = arr[i-1][j-1] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]。查询子矩阵和也用类似容斥公式：sum = pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1]。它们都是前缀和思想的变体，解决不同场景的区间问题。