今天中午不知怎么的对这个东西产生了兴趣，感觉很神奇，结果花了一个中午多的时间来看QAQ
下面说下自己的理解。
高维前缀和一般解决这类问题：
对于所有的(i,0leq ileq 2^n-1)，求解(sum_{jsubset i}a_j)。
显然，这类问题可以直接枚举子集求解，但复杂度为(O(3^n))。如果我们施展高维前缀和的话，复杂度可以到(O(ncdot 2^n))。
说起来很高级，其实代码就三行：
for(int j = 0; j < n; j++) for(int i = 0; i < 1 << n; i++) if(i >> j & 1) f[i] += f[i ^ (1 << j)];相信大家一开始学的时候就感觉很神奇，这是什么东西，这跟前缀和有什么关系？
好吧，其实看到后面就知道了。
二维前缀和
一维前缀和就不说了，一般我们求二维前缀和时是直接容斥来求的：
[ sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}-sum_{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++) a[i][j][k] += a[i - 1][j][k];for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= n; k++) a[i][j][k] += a[i][j - 1][k];for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= n; k++) a[i][j][k] += a[i][j][k - 1];高维前缀和
接下来就步入正题啦。
求解高维前缀和的核心思想也就是一维一维来处理，可以类比二维前缀和的求法稍微模拟一下。
具体来说代码中的(f[i] = f[i] + f[i xor (1 << j)])，因为我们是正序枚举，所以(i xor (1 << j))在当前层，而(i)还在上层，所以我们将两个合并一下就能求出当前层的前缀和了QAQ。
然后...就完了，好像没什么好说的。
那这跟子集有啥关系？在二进制表示中，发现当(isubset j)时，其实这存在一个偏序关系，对于每一位都是这样。而我们求出的前缀和就是满足这个偏序关系的。
回到开始那个问题，初始化(f[i]=a_i)，直接求高维前缀和，那么最终得到的(f)就是答案数组了。
理解了子集过后，我们将二进制中的每一个(1)当作(0)对待，(0)当作(1)对待求出来的就是超集了~相当于从另一个角出发来求前缀和。
求超集代码如下：
似乎(FMT)(快速莫比乌斯变换)就是借助高维前缀和这个东西来实现的。
虽然只有三行代码，但很神奇QAQ
arc 100E
题意：
给出(2^n)个数：(a_0,a_1,cdots,a_{2^n-1})。
之后对于(1leq kleq 2^n-1)，求出：(a_i+a_j)的最大值，同时(i or jleq k)。
思路：
挺奇妙的一个题，需要将问题转换。
注意一下细节，集合中一开始有一个数。
代码如下：
转载于:https://www.cnblogs.com/heyuhhh/p/11585358.html