高维前缀和：从基础概念到实际应用

创作时间:

作者:

@小白创作中心

高维前缀和：从基础概念到实际应用

引用

来源

https://www.cnblogs.com/dcytrl/p/18406487

高维前缀和是一种在算法竞赛中常用的优化技术，主要用于解决多维数组的前缀和计算问题。相比于传统的容斥方法，高维前缀和能够将时间复杂度从(O(n^w2^w))降低到(O(n^ww))，在处理大规模数据时具有显著的优势。本文将从基础概念出发，逐步介绍高维前缀和的实现方法及其在实际问题中的应用。

基础概念

让我们从一维前缀和开始回顾：

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

对于二维前缀和，我们通常使用容斥原理：

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

三维前缀和的计算会更加复杂：

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

如果维度继续增加，使用传统方法的时间复杂度会迅速上升到(O(n^w2^w))。因此，我们需要寻找更高效的解决方案。

核心思路

高维前缀和的核心思想是逐维计算前缀和。以二维前缀和为例：

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

这种方法的时间复杂度降低到了(O(n^ww))。下图直观地展示了这种计算方式：

应用场景

问题1：二进制前缀和

给定(2^n)个数(a_i)，从(0)开始标号。令(f_S)为(\sum_{T\operatorname{or} S=S}a_T)，对(S=0\sim 2^n-1)求(f_S)。(n\le 20)。

显然，一个暴力解法的时间复杂度是(O(4^n))。将(S)的每一个二进制位视为一个维度，那么(f_S)就相当于对所有这些维度做高维前缀和，每一维只有0/1两种取值。代码实现如下：

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

时间复杂度为(O(2^nn))。

问题2：狄利克雷前缀和

题目链接：https://www.luogu.com.cn/problem/P5495

要求对所有(x=1\sim n)计算(f_x=\sum_{y|x} a_y)。(n\le 2\times10^7)。

将数(x)唯一分解成(x=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k})的形式，把每个质因数视为一个维度，对所有维度做一遍高维前缀和。由于每一维的取值是在(0)到(\dfrac{n}{p})之间的，时间复杂度为(\sum_{p\in prime}\dfrac{n}{p}=O(n\log \log n))。代码实现如下：

for(int i=2;i<=n;i++){
    if(!flag[i]){//flag[i]为质数标记 
        for(int j=1;i*j<=n;++j){
            flag[i*j]=1;
            a[i*j]+=a[j];
        }
    }
}