【数论】高维前缀和 笔记

· · 算法·理论

简介

对于所有的 0\le i\le 2^n-1 ，求解 \sum^{}_{j\in i}a_j。

其中，j\in i 表示在二进制下，(1<<j) \& i=1。

数据范围：n\le20。

朴素解法

可以通过子集枚举求解，时间复杂度 O(\sum^{n}_{i=0}C^i_n\times 2^i)=O(3^n)，但使用高维前缀和求解，时间复杂度降为 O(n\times2^n)。

高维前缀和

引入

先考虑二维前缀和的情况，一般使用容斥原理求解，

sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}+a_{i,j}

代码：

for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];

但可以换一种写法，容易发现，这种写法得到的结果是相同的：

for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        a[i][j]+=a[i-1][j];
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        a[i][j]+=a[i][j-1];

则 a 数组即为所求，其中 i-1 与 j-1 的次序不影响答案。

同理，可以扩展到三维，而且比容斥原理可扩展性更强，更容易推广到高维。

for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)
            a[i][j][k]+=a[i-1][j][k];
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)
            a[i][j][k]+=a[i][j-1][k];
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)
            a[i][j][k]+=a[i][j][k-1];

高维前缀和

如果推广到更高维，代码可能是这样的：

for(int i[1]=1;i[1]<=n;i[1]++)
    for(int i[2]=1;i[2]<=n;i[2]++)
        //...
        a[i[1]][i[2]][i[3]]...+=a[i[1]-1]...;
...

这样写肯定是不行的，但考虑到原题中，一共有 n 维，每维却只有两个状态，于是可以二进制压缩，变成了这样：

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

经评论区大佬指出，这就是状压DP。

那于是问题解决，时间复杂度 O(n\times2^n)。

例题：P5495

同时，此算法是 \text{FMT} （快速莫比乌斯变换）的前缀知识。

参考资料

高维前缀和总结，%%%