题目定位
它是一维前缀和的自然二维扩展，利用容斥就能在 O(1) 内得到任意子矩形和。
关键观察
任意子矩形和都等于大前缀减去两块重叠区域，再加回公共角落。
目标复杂度
O(1) query / O(mn)
这题的解法思路怎么拆
1
它是一维前缀和的自然二维扩展，利用容斥就能在 O(1) 内得到任意子矩形和。
2
任意子矩形和都等于大前缀减去两块重叠区域，再加回公共角落。
3
先定义累计状态代表什么。
4
一趟扫描构造前缀。
参考实现
Python# Generic pattern template
prefix = [0] * (len(nums) + 1)
for i, value in enumerate(nums):
prefix[i + 1] = prefix[i] + value
range_sum = prefix[r + 1] - prefix[l]
常见坑点
warning
容斥时忘了加回重叠部分。
warning
构造前缀矩阵时行列偏移写乱。
高频追问
如果矩阵支持更新，数据结构会怎么变？
为什么前缀矩阵通常要多开一行一列？
继续刷相关题
先把 前缀和 这个模式刷成体系，再去做更难变体。