高维前缀和(SOSDP)

高维前缀和，又叫SOSDP，Sum over Subsets dynamic programming，它一般是用来解决子集类的求和问题（虽然也可以解决高维空间的求和问题，但是时空往往不允许）。

高维度下求前缀和时，时间复杂度的瓶颈

先看一下前缀和的式子

一维： $s\left[ i \right] =a[i]+s[i-1]$

二维： $s\left[ i \right] \left[ j \right] =a[i][j]+ s[i-1][j]+s[i][j-1] -s[i-1][j-1]$

三维： $s\left[ i \right]\left[ j \right]\left[ k \right] =s[i][j][k]=a[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][j-1]+s[i-1][j-1][k-1]$

....

我们发现这步容斥操作在高纬度下不能被视为O(1)，它与维度k成幂函数的关系。

高维前缀和的时间复杂度为O(|高维空间容量|* $2^k$ )，在高维空间容量不大，但是维度数很高的时候，瓶颈在于维度数k。

想办法进行优化。

另一种求前缀和的方式

for(int i=1;i<=n;++i)//先求数组a关于第一个维度的前缀和
{
    for(int j=1;j<=m;++j)
    {
        a[i][j]=a[i][j]+a[i][j-1];
    }
} 
for(int i=1;i<=n;++i)//在已经求完一个维度前缀和的基础上求数组a关于第二个维度的前缀和
{
    for(int j=1;j<=m;++j)
    {
        a[i][j]=a[i][j]+a[i-1][j];
    }
}

这种方式可以理解成二维前缀和是数组在求完关于第一个维度的前缀和，然后再for一遍求它关于第二个维度的前缀和。

然后它在求三维以上前缀和的时候，就体现出这种写法在高维前缀和上的优越性了。

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

这样的话无需借助容斥原理，求高维前缀和的复杂度变为O(|高维空间容量|*k)，可以处理k稍大一些的情况。

子集求和类问题

现在有n $(n \leq 20)$ 个物品，确定每个物品的选取与否可以表示一个集合，那么这n个物品最多可以表示 $2^n$ 个集合。现在对每个集合都给定个权值，然后查询某个集合以及其包含的所有子集的权值和。

先考虑n=2的情况。

开一个二维数组a[2][2]表示选取关系第一个维度的数字为0表示不选第一件物品，第一个维度的数字为1表示选第一个物品。同理第二个维度的数字为0表示不选第二件物品，第二个维度的数字为1表示选第二个物品。我们用s[2][2]表示两个物品选取关系下子集的和。

n=2的集合有四种：

（0,0）全不选

（1,0）只选第一件

（0,1）只选第二件

（1,1）全选

s[0][0]=a[0][0]

s[0][1]=a[0][0]+a[0][1]

s[1][0]=a[0][0]+a[1][0]

s[1][1]=a[0][0]+a[0][1]+a[1][0]+a[1][1]

然后发现如果要求某个集合以及其子集的和，其实就是它对应的二维前缀和。

发现结论在k维下也是成立的。

那么这个结论可以推广到一般，用状压DP可以实现这个前缀和操作。

for(int i=0;i<w;++i)//依次枚举每个维度
{
    for(int j=0;j<(1<<w);++j)//求每个维度的前缀和
    {
        if(j&(1<<i))s[j]+=s[j^(1<<i)]; 
    }
}

求出来的前缀和也就是某个集合的子集和，所以可以利用它维护静态的子集信息。

当然它不止可以求前缀和，前缀积，前缀max，前缀min都可以。