算是个小知识点吧
对于常见的前缀和，正常人知道的求法是通过容斥
（为了方便表示就用了 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]
而高维前缀和是对于二进制的\(n\)个维度\(arr[2][2][2][2][2]...\)，求出\(sum[2][2][2][2][2]...\)
（换成\(n\)个数的\(arr[1,n]\)数组就是求所有子集的和）
就刚才第二种的原地求和算法，可以模拟出从低位到高位维度的求和过程
（为了方便枚举位就用了 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 的最简单形式。。）