高维前缀和

高维前缀和（High-Dimensional Prefix Sum）是一种处理高维数据前缀和的技术，常用于动态规划、组合数学和位运算相关的优化问题（如子集和问题、超立方体上的求和）。其核心思想是将多维空间的前缀和计算分解为多个一维前缀和的计算，从而将时间复杂度从指数级降低到线性（相对于维度）。

一、热身运动：从一维到二维

我们先回顾一下熟悉的前缀和。

1. 一维前缀和

给你一个数组 a[1...n]，求它的前缀和 s[i] = a[1] + ... + a[i]。
这太简单了，一个 for 循环搞定：
s[i] = s[i-1] + a[i]

它的本质是什么？
s[i] 存储了“所有下标小于等于 i 的元素的和”。

2. 二维前缀和

给你一个二维数组（矩阵）a[i][j]，求它的前缀和 s[i][j]，表示以 (1,1) 为左上角，(i,j) 为右下角的矩形内所有元素的和。
我们也熟悉它的递推公式：
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]

这背后隐藏着什么思想？
s[i][j] 存储了“所有第一维下标 x ≤ i 且 第二维下标 y ≤ j 的元素的和”。

观察一下：

• 一维是解决 x ≤ i 的问题。
• 二维是解决 x ≤ i 且 y ≤ j 的问题。

那么，三维前缀和呢？就是解决 x ≤ i 且 y ≤ j 且 z ≤ k 的问题。
四维、五维… N维呢？都是一个道理。

二、升维打击：另一种计算二维前缀和的思路

刚才那个二维前缀和的公式，是容斥原理得来的。现在我们换一种思路，一种更符合“高维”思想的思路。

目标： 求 s[i][j]，即 sum(a[x][y]) 其中 x ≤ i, y ≤ j。

我们可以分两步走：

第1步：只考虑第一维
我们先不管第二维，对矩阵的每一行都做一次一维前缀和。
for i from 1 to R:
for j from 1 to C:
a[i][j] = a[i][j] + a[i][j-1]

执行完这一步后，a[i][j] 的新含义变成了：第 i 行，从第 1 列到第 j 列所有原始元素的和。
即 a[i][j] (新) = ∑ a[i][k] (原)，其中 1 ≤ k ≤ j。

第2步：再考虑第二维
现在，在已经更新过的矩阵上，我们对每一列再做一次一维前缀和。
for j from 1 to C:
for i from 1 to R:
a[i][j] = a[i][j] + a[i-1][j]

执行完这一步后，a[i][j] 的最终含义是什么呢？
它等于 (新的 a[i-1][j]) + (新的 a[i][j])
= (第 i-1 行，前 j 列的和) + (第 i 行，前 j 列的和)
= (从第 1 行到第 i-1 行，每一行的前 j 列的和) + (第 i 行，前 j 列的和)
= 从第 1 行到第 i 行，每一行的前 j 列的和
这不就是我们想要的二维前缀和 s[i][j] 吗！

总结一下这个新方法：
我们没有用复杂的容斥，而是按维度，依次进行一维前缀和。

1. 先固定行，对所有列做前缀和。
2. 再固定列，对所有行做前缀和。

这个思路可以轻松推广到任意维度！

三、主角登场：高维前缀和

现在，假设我们有一个 D 维的“数组” a[i₁][i₂]...[i_D]。
我们要计算它的前缀和 s[i₁][i₂]...[i_D]，它表示的是所有满足 x₁ ≤ i₁ 且 x₂ ≤ i₂ 且 … 且 x_D ≤ i_D 的元素的和。

高维前缀和的算法就是：

对每一个维度 d 从 1 到 D，依次进行一次“一维前缀和”操作。

伪代码：

// D 是维度数
// N 是每个维度的最大长度
for d from 1 to D: // 枚举是哪个维度
  for i_1 from 1 to N_1: // 枚举第一个坐标
    for i_2 from 1 to N_2: // 枚举第二个坐标
      ...
      for i_D from 1 to N_D: // 枚举第 D 个坐标
        // 关键一步：只在第 d 维上做前缀和
        if i_d > 1:
          a[i_1]...[i_d]...[i_D] += a[i_1]...[i_d - 1]...[i_D]

这个伪代码看起来很吓人，有很多层 for 循环。但它的核心思想就是我们刚才讲的二维的例子。

时间复杂度：
每一维的计算，都需要遍历整个 N₁*N₂*...*N_D 的数据。我们总共有 D 个维度。
所以总时间复杂度是 O(D * N₁ * N₂ * … * N_D)。

四、从“前缀和”到“子集和”：一个重要的变体

在 OI 比赛中，高维前缀和最常见的应用场景并不是处理几何上的多维空间，而是处理位运算中的“子集”问题。

问题：
有一个数组nums，我们想计算一个新的数组 s，其中 s[mask] 等于所有 submask 是 mask 的子集（submask | mask == mask）的 a[submask] 的和。
即 s[mask] = ∑ a[submask]，其中 submask 是 mask 的子集。

这怎么就和高维前缀和扯上关系了？
我们可以把一个 N 位的二进制数，看成是一个 N 维空间中的点！

一个数 mask，它的二进制表示是 (b_{N-1} b_{N-2} ... b_0)。
我们可以把它看成是一个 N 维空间中的点 (b_{N-1}, b_{N-2}, ..., b_0)，这个空间的特殊之处在于，每个坐标只能是 0 或 1。

那么，“submask 是 mask 的子集”这个条件，用坐标来描述是什么意思？
submask | mask == mask 意味着，如果 mask 的第 i 位是 0，那么 submask 的第 i 位也必须是 0。如果 mask 的第 i 位是 1，submask 的第 i 位可以是 0 也可以是 1。

这正好对应了我们前缀和的定义！
s[mask] = s[b_{N-1}...b_0] = ∑ a[x_{N-1}...x_0]，其中对于所有 i，x_i ≤ b_i。

所以，求“子集和”的问题，完全等价于在一个 N 维，每维大小为 2（坐标只能是0或1）的空间里做高维前缀和！

代码实现（子集和/SOS DP）：
这个版本的代码更常用，也更简洁。SOS DP (Sum over Subsets) 是它的另一个名字。

def sumOverSubnets(nums):
    N = max(nums).bit_length()
    print(N)
    s = [0] * (1 << N)
    for v in nums:
        s[v] = v
    for i in range(0, N):
        for mask in range(1 << N):
            if mask & (1 << i):
                s[mask] += s[mask ^ (1 << i)]
    return s


if __name__ == '__main__':
    nums = [1, 2, 3, 4, 5, 6, 7]
    print(nums)
    print(sumOverSubnets(nums))

时间复杂度： O(nlogn)。

五、总结（划重点）

1. 高维前缀和是干嘛的？

   计算 D 维空间中，s[i₁]...[i_D] = ∑a[x₁]...[x_D] (其中 x_k ≤ i_k for all k)。它是普通前缀和向高维的自然推广。

2. 核心思想是什么？

   降维打击。不要一次性考虑所有维度，而是按维度逐个击破。对每一个维度，都做一次一维前缀和的计算。

3. 在OI中，最常见的应用是什么？

   子集和问题 (Sum over Subsets, SOS DP)。把一个 N 位的二进制数 mask 看成 N 维空间中的一个点 (b_{N-1}, ..., b_0)。求 mask 的所有子集的和，就等价于求这个点的高维前缀和。

4. 子集和的代码怎么写？

   两层循环。外层循环 i 从 0 到 N-1（枚举维度），内层循环 mask 从 0 到 2^N-1（枚举所有状态）。
   if (mask & (1 << i))，则 dp[mask] += dp[mask ^ (1 << i)]。

高维前缀和/SOS DP 是一个非常强大的工具，能解决很多和位运算、子集、超集相关的计数问题，是进阶选手必须掌握的技巧之一。

详见：高维前缀和 SOS DP