算是个小知识点吧
对于常见的前缀和,正常人知道的求法是通过容斥
(为了方便表示就用了1开始的下标和伪代码)
loop i:[1,x] loop j:[1,y] loop k:[1,z]
sum[i][j][k] = arr[i][j][k]
+ sum[i-1][j][k] + sum[i][j-1][k] + sum[i][j][k-1]
- sum[i-1][j-1][k] - sum[i-1][j][k-1] - sum[i][j-1][k-1]
+ sum[i-1][j-1][k-1]
其实还有更低复杂度的写法
loop i:[1,x] loop j:[1,y] loop k:[1,z] arr[i][j][k] += arr[i][j][k-1]
loop i:[1,x] loop j:[1,y] loop k:[1,z] arr[i][j][k] += arr[i][j-1][k]
loop i:[1,x] loop j:[1,y] loop k:[1,z] arr[i][j][k] += arr[i-1][j][k]
而高维前缀和是对于二进制的个维度,求出
(换成个数的数组就是求所有子集的和)
就刚才第二种的原地求和算法,可以模拟出从低位到高位维度的求和过程
(为了方便枚举位就用了0开始的下标)
for(int j = 0; (1<<j) < n; j++)
for(int i = 0; i < n; i++)
if(i>>j&1) arr[i] += arr[i^(1<<j)];
// 因为每一维就只有0和1,因此对于i的第j位xor一下就是1变为0
(这tm就是状压DP的最简单形式。。)