高维前缀和与 SOSDP

高维前缀和

高维前缀和，就是对每一个高维空间的点 \((a_1,a_2,\cdots,a_k)\) ，求 \(\displaystyle \sum_{b_1=0}^{a_1} \sum_{b_2=0}^{a_2}\cdots \sum_{b_k=0}^{a_k} val_{(b_1,b_2,\cdots,b_k)}\)

一种做法是容斥，大概就是求出除了 \((a_1,a_2,\cdots,a_k)\) 之外的所有点之和。复杂度 \(\mathcal O(n^k\cdot 2^k)\)

以二维为例：

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

另一种做法是降维，即每次只考虑一个求和号做线性前缀和。复杂度 \(\mathcal O(n^k\cdot k)\)

仍以二维为例：

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

SOSDP

即求子集权值和。考虑到这等价于一个高维前缀和问题。

直接给出代码：

// f[s] 初始值为 val[s]
for(int i=0;i<k;++i)
    for(int s=0;s<(1<<k);++s)
        if(s&(1<<i)) f[s]+=f[s^(1<<i)]