读完这篇文章你会彻底理解为什么高维前缀和里奇数个下界要减偶数个下界要加——而且这辈子都不会忘。0. 先讲个故事小明在刷一道二维前缀和的题。题目很简单给一个矩阵求某个子矩阵里的元素和。sum S[y₂][x₂] - S[y₁-1][x₂] - S[y₂][x₁-1] S[y₁-1][x₁-1]他背下了这个公式——左上角加两边减中间加。考过了。几周后小明遇到一道三维前缀和的题。他懵了——三维有 2³ 8 种组合哪些加哪些减他开始现场推推错了。再后来他遇到一道D 维的题。彻底崩了。小明的问题在哪他只背了结果没理解为什么。这篇文章就是写给所有小明的。我们来从头推一遍让你彻底理解高维前缀和背后的数学本质——容斥原理。1. 问题是什么1.1 一维热身一维前缀和大家都会sum[l, r] prefix[r] - prefix[l-1]其中prefix[i]表示从开头到位置 i 的和。直觉很简单要区间 [l, r] 的和用从开头到 r减去从开头到 l-1。1.2 二维开始出现组合二维前缀和S[x][y] Σ(i1..x) Σ(j1..y) a[i][j]查询子矩阵 (x₁, y₁) 到 (x₂, y₂) 的和sum S[x₂][y₂] - S[x₁-1][y₂] - S[x₂][y₁-1] S[x₁-1][y₁-1]符号规律四个项选0 个下界全取上界正号选1 个下界x₁-1 或 y₁-1负号选2 个下界又是正号。取了下界的维度数符号0全取上界1 个−2 个下界 ( 上面下界指的是x1-1和y1-1 ) 个数为偶数 → 正号下界个数为奇数 → 负号。1.3 D 维通用公式查询区间 ∏ [Lₖ, Rₖ] 的和ans Σ(mask0..2ᴰ⁻¹) (−1)^popcount(mask) · S[根据mask每维取R或L-1]其中mask的二进制第 k 位为1→ 该维取下界减一Lₖ−1为0→ 取上界Rₖpopcount(mask) mask 二进制中1的个数(−1)^popcount(mask) 偶数个 1 为正奇数个 1 为负这就是大家常说的奇减偶加。但要真正理解它我们需要深入——容斥原理。2. 容斥原理一切的根本2.1 一个幼儿园级别的例子你班上有 30 个学生15 个人喜欢打篮球12 个人喜欢踢足球5 个人两个都喜欢问有多少人至少喜欢一个直接 15 12 27不对——那 5 个被算了两次。正确答案15 12 − 5 22。这个减去重叠部分的思想就是容斥原理的雏形。2.2 形式化表述对于 n 个集合 A₁, A₂, ..., Aₙ它们的并集大小是|A₁ ∪ A₂ ∪ ... ∪ Aₙ| Σ|Aᵢ|−Σ|Aᵢ∩Aⱼ|Σ|Aᵢ∩Aⱼ∩Aₖ|− ... (−1)ⁿ⁻¹|A₁∩...∩Aₙ|用人类语言说就是并集的大小 单个集合之和 − 两两交集之和 三三交集之和 − 四四交集之和 ...符号交替的原因先加所有单个集合 → 重叠被重复计算 → 减去两两交集 → 三重重叠被减多了 → 加回来 → 以此类推。2.3 换个等价说法更贴合前缀和场景容斥原理的补集版本|A̅₁ ∩ A̅₂ ∩ ... ∩ A̅ₙ| |U| − Σ|Aᵢ| Σ|Aᵢ∩Aⱼ| − Σ|Aᵢ∩Aⱼ∩Aₖ| ...其中 U 是全集A̅ᵢ 表示不具备属性 Aᵢ。一个坏属性都没有 全集 − 有 1 个坏属性的 有 2 个坏属性的 − 有 3 个坏属性的 ...3. 映射到前缀和问题现在让我们把前缀和问题精确地映射到容斥原理上。3.1 定义全集和坏属性全集 U所有满足 0 ≤ Sₖ ≤ Rₖ每维 ≤ 上界的点 → 对应S[R₁][R₂]...[RD]坏属性 Aₖ第 k 维越界了即坐标 Lₖ也就是 Sₖ ≤ Lₖ−1目标找一个坏属性都没有的点 → 每维都在 [Lₖ, Rₖ] 内的合法点3.2 代入容斥公式合法点数 全集 − (有1个坏属性) (有2个坏属性) − (有3个坏属性) ...每一项怎么算全集0 个坏属性S[全取上界]1 个坏属性第 k 维越界S[第k维取 Lₖ−1, 其余取 R]2 个坏属性第 i,j 维同时越界S[第i,j维取 L−1, 其余取 R]关键观察每一项 S[...] 的参数中有几个维度取了下界Lₖ−1就有几个坏属性。容斥原理告诉我们——奇数个坏属性 → 减号偶数个坏属性 → 加号。3.3 这就是奇减偶加的终极来源用二进制枚举mask 从 0 到 2ᴰ−1mask 第 k 位为1→ 第 k 维取 Lₖ−1声明坏属性popcount(mask) 坏属性个数(−1)^popcount(mask) 容斥原理赋予的符号奇减偶加不是什么魔法它就是容斥原理公式的直接翻译。4. 严格证明为什么不会多算也不会少算4.1 证明框架对空间中任意点 P分析它在 2ᴰ 项求和中被统计的次数P 在区间内合法→ 应统计恰好1次P 不在区间内非法→ 应统计0次完全抵消4.2 情况一合法点P 在每个维度的坐标都在 [Lₖ, Rₖ] 内 →没有任何坏属性。P 只在全取上界那一项mask0被包含。任何带下界的项都覆盖不到 P因为 P 在该维坐标 ≥ Lₖ Lₖ−1。→ P 被统计恰好1次4.3 情况二非法点设 P 在 m 个维度上越界m ≥ 1越界维度集合为 A|A|m。引理对任意 maskP 被该项包含 ⇔ mask 中所有值为1的维度都在 A 中。→ P 能被包含的项 A 的所有子集共 2ᵐ 种组合。符号取决于子集大小popcountTotal C(m,0) − C(m,1) C(m,2) − ... (−1)ᵐ·C(m,m)4.4 二项式定理(1 − 1)ᵐ C(m,0) − C(m,1) C(m,2) − ... (−1)ᵐ·C(m,m)由于 m ≥ 1(1 − 1)ᵐ 0ᵐ 04.5 证明完成任何非法点至少在一个维度越界经过这 2ᴰ 项奇偶交替的加减之后被统计的总次数永远、完美地等于 0。核心就一句话非法点被包含的次数之和 (1−1)ᵐ 0。当你脑海中浮现出这个画面——合法点被算 1 次非法点被算 0 次。5. 可视化二维和三维的直观理解5.1 二维查询 [x₁, x₂] × [y₁, y₂]S[x₂][y₂] 包含了整个大矩形含不需要的部分 − S[x₁−1][y₂] 减去左边的多余矩形 − S[x₂][y₁−1] 减去下边的多余矩形 S[x₁−1][y₁−1] 左下角被减了两次加回来这就是容斥在二维的直观表现加大的减多出一次的补回多减掉的。5.2 三维查询 [x₁, x₂] × [y₁, y₂] × [z₁, z₂]2³ 8 项 S[Rₓ][R_y][R_z] 全上界 − S[Lₓ−1][R_y][R_z] x 维取下界 − S[Rₓ][L_y−1][R_z] y 维取下界 − S[Rₓ][R_y][L_z−1] z 维取下界 S[Lₓ−1][L_y−1][R_z] x,y 取下界 S[Lₓ−1][R_y][L_z−1] x,z 取下界 S[Rₓ][L_y−1][L_z−1] y,z 取下界 − S[Lₓ−1][L_y−1][L_z−1] x,y,z 全取下界符号序列, −, −, −, , , , −— 恰好按 popcount 奇偶交替。6. 代码实现理解了原理代码就是水到渠成的事// D 维前缀和查询 // prefix 是 D 维前缀和数组 // L[i], R[i] 分别是第 i 维的查询下界和上界 long long query(int D, vectorint L, vectorint R) { long long ans 0; for (int mask 0; mask (1 D); mask) { vectorint coord(D); for (int k 0; k D; k) { if (mask k 1) coord[k] L[k] - 1; // 取下界-1声明坏属性 else coord[k] R[k]; // 取上界 } int sign (__builtin_popcount(mask) 1) ? -1 : 1; ans sign * prefix[coord]; } return ans; }__builtin_popcount(mask) 1判断奇偶奇数 → −1减偶数 → 1加。