高维前缀和详解
背景：
sensei：我们随便上点技巧类型的东西吧，就这个高位前缀和......(讲了一堆k维前缀和复杂度证明后）......好我们看看版题。
版题：
现在有n(n≤20)个物品，确定每个物品的选取与否可以表示一个集合，那么这n个物品最多可以表示个2的n次方个集合。
现在对每个集合都给定个权值，然后查询某个集合以及其包含的所有子集的权值和。
sensei：很简单吧，直接用高维就好了。
我：？？？高维在哪里？？？
现实版的高维前缀和（真就k维这样）
引入：
我们拿k=2来进行引入：
一般的二维前缀和是利用的容斥原理,加加减减四项好好写哦。
k=3，没关系，稍微复杂点而已。
k=20，没关系，自毙了而已。
OI大神：无所谓我可以慢慢熬。
sosdp:您加油，我先A了。
写法：
那么高级的前缀和怎么写：对于每一维上轮流求前缀和。
k=2:
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];
}
}
k=3:
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];
}
}
}
这样写的意义：
假设我们求的是k维前缀和，对于原来的算法，我容斥原理要计算2的n次方次，已经不是常数了......
现在这个新的算法的时间就是k*容量了，大大减少时间复杂度和思考程度
抽象的高维前缀和
引入：
现实版高维前缀和倒下了。
某OIer：就这就这就这？？？
抽象版高维前缀和上场了。
OIer倒下了。
求解子集/超集：就这就这就这？？？
正文：
现在我们考虑抽象的高位前缀和：子集和超级。
我们先拿子集来说。
对于长度为2的情况，有四种情况:01/00/11/10。
放到二维平面上考虑
我们想求在这四种情况下的权值和，a00+a01+a10+a11，发现正是二维前缀和！
很显然这种情况可以扩展到k维，取到的前缀和就表示长度为k的子集的权值和。
然后我们会发现：a数组的k个维度都是0或者1，那我们可以用bitset或者一个二进制数直接表示整体（这样就不用开k维数组了）
代码如下：
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)];
}
}