引入方法
在讨论高维前缀和前，不妨先回顾以下二维前缀和，一种写法是：
for(int i = 1; i <= w; i++)
for(int j = 1; j <= w; j++)
sum[i][j] += sum[i][j - 1]
for(int i = 1; i <= w; i++)
for(int j = 1; j <= w; j++)
sum[i][j] += sum[i - 1][j]
推广到 \(n\) 维就是：
for(int x1 = 1; x1 <= w; x1++)
for(int x2 = 1; x2 <= w; x2++)
...
for(int xn = 1; xn <= w; xn++)
sum[x1][x2]...[xn] += sum[x1 - 1][x2]...[xn]
for(int x1 = 1; x1 <= w; x1++)
for(int x2 = 1; x2 <= w; x2++)
...
for(int xn = 1; xn <= w; xn++)
sum[x1][x2]...[xn] += sum[x1][x2 - 1]...[xn]
...
for(int x1 = 1; x1 <= w; x1++)
for(int x2 = 1; x2 <= w; x2++)
...
for(int xn = 1; xn <= w; xn++)
sum[x1][x2]...[xn] += sum[x1][x2]...[xn - 1]
解决问题
它有什么用吗？看这个问题：
计算所有的 \(f(S)=\sum_{T \in S} g(T)\)。
暴力枚举子集时间复杂度为 \(O(3^n)\)。其中 \(n = |S|\)。
但使用高维前缀和可以优化到 \(O(n2^n)\)。
不难发现，对于每个元素，只有选与不选两种可能，可以记作 \(0/1\)。不妨看作有 \(n\) 维，每维的空间大小都是 \(2\)。对于一个 \(1\)，可以允许 \(0/1\)；对于一个 \(0\)，可以允许 \(0\)。
实际上就是在求一个高维前缀和，我们可以状态压缩成一个二进制数，然后模拟上述过程即可。
代码实现如下：
for(int i = 0; i < n; i++)
for(int j = 0; j < (1 << n); j++)
if(j & (1 << i)) f[j] += f[j ^ (1 << i)];
例题讲解
一、P5495 【模板】Dirichlet 前缀和：
题意：
给定一个长度为 \(n\) 的数列 \(a_1,a_2,a_3,\dots,a_n\)。
现在你要求出一个长度为 \(n\) 的数列 \(b_1,b_2,b_3,\dots,b_n\)，满足：
\[b_k=\sum_{i|k}a_i \]
\(n \le 2 \times 10^7\)。
分析：
考察对高维前缀和的理解。
对于一个 \(a\)，它对 \(b\) 有贡献当且仅当 \(p_{i} \le q_{i}\)，其中 \(a=\prod_{P \in prim} P^{p_{i}},b=\prod_{P \in prim} P^{q_{i}}\)。
把每个质数看成一维，那么就是在求一个高维前缀和。可以直接用这个数的值表示它的状态。
枚举每个质数，加上除去这个质数的答案。
具体来说就是这样算：
for(int i = 2; i <= n; i++) {
if(f[i]) continue; //f[i]表示是否是合数
for(int j = 1; i * j <= n; j++)
a[i * j] += a[j];
}
二、[ARC100E] Or Plus Max
题意：
给你一个长度为 \(2^n\) 的序列 \(a\)，每个\(1\le K\le 2^n-1\)，找出最大的 \(a_i+a_j\)（\(i \mathbin{\mathrm{or}} j \le K\)，\(0 \le i < j < 2^n\)）并输出。
\(n \le 18,a_{i} \le 10^9\)。
分析：
对于每个 \(K\)，我们可以去求 \(i \in K\) 的最大值与次大值，作为 \(i\) 与 \(j\)，然后对 \(K-1\) 的答案取 \(\max\) 即可。
容易发现这样做不存在一对 \(i,j\) 本来不能被统计而被统计了，也不存在本来应该被统计而没被统计。
高维前缀 \(\max\) 即可。
三、[CF1208F] Bits And Pieces
题意：
给定 \(n\) 个数的数组 \(a\)，找到 $i\lt j\lt k $ 的 \(i,j,k\)，使得 \(a_i|(a_j \& a_k)\) 最大。
\(n \le 10^6,a_{i} \le 2 \times 10^6\)。
分析：
考虑枚举 \(i\)，然后从高往低位贪心。
- \(a_{i}\) 的第 \(j\) 位为 \(1\)，没有任何限制条件，当前答案直接加上
1<<j即可。 - \(a_{i}\) 的第 \(j\) 位为 \(0\)。增加限制条件，利用高维前缀和维护一个满足这个限制条件的数的位置的最大值与次大值，如果能找到更新答案，否则恢复成原来的限制条件。
时间复杂度 \(O(n \log w+w \log w)\)。