高维度数组求前缀和

例如4维数组f[d1][d2][d3][d4]，每个维度分别为d1,d2,d3,d4

int f[d1][d2][d3][d4];
for (int i1=1; i1<d1; i1++) {
    for (int i2=1; i2<d2; i2++) {
        for (int i3=1; i3<d3; i3++) {
            for (int i4=1; i4<d4; i4++) {
                f[i1][i2][i3][i4] += f[i1][i2][i3][i4-1];
            }
        }
    }
}
for (int i1=1; i1<d1; i1++) {
    for (int i2=1; i2<d2; i2++) {
        for (int i3=1; i3<d3; i3++) {
            for (int i4=1; i4<d4; i4++) {
                f[i1][i2][i3][i4] += f[i1][i2][i3-1][i4];
            }
        }
    }
}
for (int i1=1; i1<d1; i1++) {
    for (int i2=1; i2<d2; i2++) {
        for (int i3=1; i3<d3; i3++) {
            for (int i4=1; i4<d4; i4++) {
                f[i1][i2][i3][i4] += f[i1][i2-1][i3][i4];
            }
        }
    }
}
for (int i1=1; i1<d1; i1++) {
    for (int i2=1; i2<d2; i2++) {
        for (int i3=1; i3<d3; i3++) {
            for (int i4=1; i4<d4; i4++) {
                f[i1][i2][i3][i4] += f[i1-1][i2][i3][i4];
            }
        }
    }
}

对于有$n$维的数组，第$i$维度为$d_i$，求前缀和其时间复杂度是$\prod \limits_{i=1}^n d_i$ 若每个维度大小都相等，$d_i=c$，那么时间复杂度是$c^n$

若$c=2$，这些下标可以用一个$n$位二进制数来表示，二进制数可以代表集合，求前缀和可以认为是求子集和。

求子集和

使用维度大小为2的高维度数组表示子集

int f[2][2][2][2];
for (int i1=1; i1<2; i1++) {
    for (int i2=1; i2<2; i2++) {
        for (int i3=1; i3<2; i3++) {
            for (int i4=1; i4<2; i4++) {
                f[i1][i2][i3][i4] += f[i1][i2][i3][i4-1];
            }
        }
    }
}
for (int i1=1; i1<2; i1++) {
    for (int i2=1; i2<2; i2++) {
        for (int i3=1; i3<2; i3++) {
            for (int i4=1; i4<2; i4++) {
                f[i1][i2][i3][i4] += f[i1][i2][i3-1][i4];
            }
        }
    }
}
for (int i1=1; i1<2; i1++) {
    for (int i2=1; i2<2; i2++) {
        for (int i3=1; i3<2; i3++) {
            for (int i4=1; i4<2; i4++) {
                f[i1][i2][i3][i4] += f[i1][i2-1][i3][i4];
            }
        }
    }
}
for (int i1=1; i1<2; i1++) {
    for (int i2=1; i2<2; i2++) {
        for (int i3=1; i3<2; i3++) {
            for (int i4=1; i4<2; i4++) {
                f[i1][i2][i3][i4] += f[i1-1][i2][i3][i4];
            }
        }
    }
}

这样非常不elegent，可以利用二进制数的特性，四重for循环可改为枚举二进制数 可以枚举4个二进制位确定是哪个下标累加

for (int i=0; i<4; i++) {
    for (int j=0; j<1<<4; j++) {
        int i1=j>>3, i2=j>>2&1, i3=j>>1&1, i4=j&1;
        f[i1][i2][i3][i4] += f[i1-(i==0)][i2-(i==1)][i3-(i==2)][i4-(i==3)];
    }
}

维度大小都是2的高维度数组，用一维数组来表示其实更好处理，只需要将下标看作n位二进制数

对于n个元素的子集，求子集和，时间复杂度$O(n2^n)$

for (int i=0; i<n; i++) {
    for (int j=0; j<1<<n; j++) {
        if (j>>i&1) f[j] += f[j^(1<<i)];
    }
}

SOS DP

高维度前缀和也称为SOS DP (Sum over Subsets dynamic programming)

以dp视角看待求子集和，$dp_{i,j}$代表只处理了二进制集合$j$的低$i$位的子集和，$dp_{0,i}$对应初始化的$f_i$

状态转移

• $j$的第$i$位为1时, $dp_{i, j} = dp_{i-1, j} + dp_{i-1, j'}$，$j'$代表$j$移除了第i位的1。
• $j$的第$i$位为0时，$dp_{i, j} = dp_{i-1,j}$

时间复杂度是$O(n2^n)$