二维前缀和数组需扩容一行一列并用0填充，原数组元素从(1,1)开始映射；查询子矩阵和时，0-based坐标需各加1再代入公式dpr2+1-dpr1-dpr2+1+dpr1。
二维前缀和数组怎么构建才不会越界
构建二维前缀和数组时，最常踩的坑是索引偏移没处理好，导致 dp[i][j] 计算时访问了不存在的 dp[i-1][j] 或 dp[i][j-1]。正确做法是让前缀和数组比原数组多一行一列，全部用 0 填充，原数组 matrix 的元素从 (1,1) 开始映射。
核心递推式是：dp[i][j] = matrix[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]。这个公式本质是容斥：把左上矩形、上方矩形、左方矩形加起来，再减掉重复计算的左上角重叠部分。
常见错误现象：IndexError: list index out of range，往往因为忘了扩容或错把 i,j 当作原数组下标直接代入。
如何用二维前缀和查任意子矩阵和（含边界细节）
给定子矩阵左上角 (r1, c1)、右下角 (r2, c2)（均为 0-based），对应前缀和数组 dp（1-based 索引），查询公式为：dp[r2+1][c2+1] - dp[r1][c2+1] - dp[r2+1][c1] + dp[r1][c1]。
立即学习“Python免费学习笔记（深入）”；
关键点在于：前缀和数组的 (i,j) 存的是从 (0,0) 到 (i-1,j-1) 的和，所以原坐标必须 +1 才能对齐。漏加这 1 就会少算一行或一列。
使用场景举例：图像像素块求和、网格中频繁查询矩形区域数值总和（如游戏地图资源统计、热力图聚合）。
- 若输入坐标是 1-based，先统一转成 0-based 再套公式
- 务必检查
r1 且 <code>c1 ，否则结果无意义 - 所有下标在代入
dp前必须保证 ≥ 0 且 ≤len(dp)
三维前缀和还能用吗？空间和时间代价是否合理
可以，但要谨慎。三维前缀和构建公式是：dp[i][j][k] = arr[i-1][j-1][k-1] + dp[i-1][j][k] + dp[i][j-1][k] + dp[i][j][k-1] - dp[i-1][j-1][k] - dp[i-1][j][k-1] - dp[i][j-1][k-1] + dp[i-1][j-1][k-1]，共 8 项，是标准容斥展开。
问题在于空间爆炸：若原始数组是 100×100×100，dp 就要占用约 100³ × 8 字节 ≈ 80 MB（Python 中每个 int 更大，实际可能翻倍）。查询一次虽仍是 O(1)，但预处理时间 O(n³) 和内存占用常成为瓶颈。
替代思路：如果查询不频繁，或只沿某一维切片查询，可考虑二维前缀和嵌套 + 一维遍历，而非硬上三维。
NumPy 里有没有现成的高效替代方案
有，但不是直接叫“prefix_sum”。最实用的是 np.cumsum 配合轴向操作，再结合切片差分。
例如二维情形：
import numpy as np arr = np.array([[1,2,3],[4,5,6],[7,8,9]]) dp = np.pad(np.cumsum(np.cumsum(arr, axis=0), axis=1), ((1,0),(1,0)), 'constant') # 然后按前述公式用 dp 查询，注意 np.pad 默认补 0
优势是底层 C 实现，构建比纯 Python 快数倍；劣势是仍需手动处理索引偏移，且三维时 np.cumsum 轴向链式调用易出错。更稳妥的做法是封装一个函数，把坐标转换和差分逻辑收进去，避免每次手算 +1/-1。
真正容易被忽略的是：NumPy 数组默认是 C-order，cumsum 沿 axis=0 是列优先累加，和数学习惯一致；但如果原始数据是 Fortran-order 或做了 transpose，结果会错位。
