我们经常要用到前缀和。
一维：
for(int i=1;i<=n;i++)b[i]=b[i-1]+a[i];
二维：
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
那如果是三维的呢？
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=p;k++) b[i][j][k]=b[i-1][j][k]+b[i][j-1][k]+b[i][j][k-1] -b[i-1][j-1][k]-b[i-1][j][k-1]-b[i][j-1][j-1] +b[i-1][j-1][k-1]+a[i][j][k];
其实就是一个容斥。
但是，随着维度t变高，容斥的复杂度是2^t，总复杂度O(n^t*2^t不能承受。
我们还有一个方法：
一维：
for(int i=1;i<=n;i++) a[i]+=a[i-1];
二维：
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]+=a[i][j-1];for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]+=a[i-1][j];
这个意思就是，第一遍前缀和，每个位置a[i][j]是，i行前j个的和。
第二遍，就把前面所有行的和加过来了。
分两遍达到目的。看似麻烦。
那三维呢？
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int p=1;p<=k;p++) 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 p=1;p<=k;p++) 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 p=1;p<=k;p++) a[i][j][k]+=a[i][j][k-1];
其实和二维的理解是一样的。再来一遍，把第三维的和加过去。
但是，这个三维只要3次，也就是说，对于t维，其实只要O(n^t*t)复杂度就很低了。
其实我们实际解题中，经常用的是n=2的情况。
比如，
例题：
1.部分和（牛客网NOIP赛前集训营-普及组（第四场））
输入一个长度为n的数组a[i]，下标从0开始（0到n-1） 保证n是2的整数次幂， 对于每个i (0 <= i < n) 求所有满足((i & j) == j)的a[j]之和。
n<=2^20
即，求每个i的子集和。
如果n=2^6,如果把i的二进制的表示：10101看做一个5维坐标的话，
那么，i的子集就是这个坐标的高维前缀和。
可以发现，每个维度的n都是2，
这就比较好处理了。
如果是一般的：w表示最高维度：
for(int i=0;i
理解一下，就是先处理前i-1位是子集的所有位置的和，对于第i位，前i位是子集的要么第i位是0，要么第i位是1，
第i位是0的话，权值就是f[j^(1<<i)]，（后面的维度坐标一定要一致。）
本题：
#includeusing namespace std;typedef long long ll;const int N=(1<<21);ll a[N];int n;int main(){ scanf("%d",&n);int p=0; for(int i=0;i
复杂度和高维前缀和一样；O(2^t*t)
upda：2019.3.18
可以代替FWT的and和or卷积，只要"IFMT"一下（就是反着做）即可
复杂度相同，
upda：2019.4.17
实际上
FMT很辣鸡
相比之下，FWT做的事情完全包含FMT，并且常数是FMT的1/2！
（这个题我人傻常数大，必须用FWT卡常才能过）
所以还是写FWT吧