浅谈高维前缀和

浅谈高维前缀和

引入

在用一般方法计算二维前缀和的时候,我们可以写出如下代码

for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        sum[i][j]=a[i][j]+sum[i][j-1]+sum[i-1][j-1]-sum[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++){
            sum[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][j-1]+sum[i-1][j-1][k-1]+a[i][j][k];
        }
    }
}

我们发现在求前缀和的时候需要一个容斥,当维数为(t)的时候容斥的时间复杂度是(2^t)，随着维数变高，复杂度增大的很快

高维前缀和的一般优化

但是，我们可以把高维前缀和的总时间复杂度从(O(n^t2^t))优化到(O(n^tt))

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

我们实际上是先对每一行求了前缀和，再把前缀和加起来。对于(sum[i][j]),第一轮for循环结束后它存储的是第i行前j个数的和。然后第二轮for循环把第1,2,3,i-1行前j个数的和加起来,就得到了二维前缀和。

高维前缀和利用了每个维度分别累加的思想，同理可以写出三维前缀和。时间复杂度(O(n^tt))

高维前缀和与二进制

其实，上面提到的这种前缀和方法不常用，因为算法竞赛中很少遇到3维以上的前缀和，而(tleq 3)时(O(n^t2^t))与(O(n^tt))差别不大。但是,如果我们把n位二进制数看成一个n维坐标，如((10101)_2)看成(sum[1][0][1][0][1]),此时维数比较高，高维前缀和的优势就很明显了。

运用状态压缩的思想,二进制高维前缀和可以处理一些集合问题.因为一个二进制数可以看成一个集合，位运算与、或对应集合的并、交。

我们考虑一个大小为(n)的集合(S),求(f(S)=sum_{T subseteq S} f(T)),那么按照高维前缀和的思想求f,可以写出如下代码

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)]; 
    }
}

(i)实际上就是在枚举当前累加的是维度,(j)枚举每个集合，存储前缀和数组的时候我们省略了维度(i).而(j)表示剩下的每个维度。

j&(1<<i)表示j包含元素i,而j^(1<<i)表示j去掉i后的集合,我们现在把i加入,就得到了f[j]

例题

//施工中