看今天银川2019网络赛K（实际上是2018）的解法，能够将o(3^n)优化到o(n*2^n).
一维前缀和:for(i=1;i<=n;++i) a[i]+=a[i-1]
二维前缀和:for(j)for(i=1;i<=n;++i) a[i,j]+=a[i-1,j];
for(i)for(j=1;j<=n;++j) a[i,j]+=a[i,j-1];
经过第一轮操作后新的a'[i,j]=\(\Sigma\)a[1..i,j], 所以第二轮操作后a''[i,j]=\(\Sigma\)a'[i,1..j]= \(\Sigma\)a[1..i,1..j].同理，对n维前缀和,我们可以逐维统计前若干维的前缀和,最后得到所有维的前缀和，即二维前缀和.

应用：已知a[1..n],对每个i求\(\Sigma_{i\&j=j}\)a[j].一般做法：对每个i枚举子集,复杂度为o(3^n).可以把每个数看作bit位组成的bit维空间,题目变成求高维前缀和.
for(i=0;i<bit;++i)for(j=1;j<=n;++j) if(j&(1<<i)) a[j]+=a[j^(1<<i)];

另一种前缀和("后缀和"):b[i]= \(\Sigma_{i\&j=i}\)a[j],方法类似.
for(i=0;i<bit;++i)for(j=1;j<=n;++j) if(~(j&(1<<i)) a[j]+=a[j|(1<<i)];