前缀和
2026-05-11
高维前缀和
类比 1,2 维前缀和,我们都可以按照每一个维度依次处理,但是对于 3 维以上,显然不能靠手写循环,不妨简单一点,每个维度只有 0 或者 1。
按照依次枚举每一维进行分别前缀和的方法,可以得到高维前缀和的代码:
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)];子集和 DP
子集和 DP,又称 SOS DP,一般问题为:考虑大小为 n 的集合的全体子集上定义的函数 f(T),现在要求其子集和函数 g(S),使其满足:
g(S)=T⊆S∑f(T)
如果直接暴力算,大小为 k 的集合共有 (kn) 个,每个集合 2k 个子集,总枚举次数为 ∑k=0n(kn)2k=3n,无法接受。
现在我们更换一下视角,考虑把长度为 n 的二进制数看做 n 维下空间中的点,每一位 0 或 1 看作坐标。
容易发现,T⊆S 的充要条件是在 n 个维度上,都有 Ti≤Si,因此求 g(S) 实际就是求其 n 维前缀和。
仿照逐维前缀和,进行一维维的合并,每次独立做一遍一维前缀和,令 f[i][S] 表示只有前 i 个位置与其不同的子集之和。
对于 Si,若其为 0,则 f[i][S]=f[i−1][S];若其为 1,则第 i 位可 0 可 1,即 f[i][S]=f[i−1][S]+f[i−1][S⊕2i]。
对于这个转移,容易发现 f[i][S] 只与 i−1 及比 S 小的下标有关,所以可以进行滚动覆盖,注意把维度 i 放在最外层即可。
