其实是个异常简单的东西……

众所周知，一维前缀和是 \(\mathrm O(n)\) 的，二维前缀和是 \(\mathrm O\!\left(n^2\right)\)（这里假定各维度值域相等）的。那么 \(d\) 维前缀和（这个唤做高维前缀和）就是 \(\mathrm O\!\left(n^d\right)\) 的？显然做不到。这是因为一、二维前缀和常数可以忽略。

那么被忽略掉的常数显然等于计算一个值的时候的式子的项数，一维是 \(2\)，二维是 \(4\)。维数多了以后，你会发现这个常数就是一个 \(d\) 维超立方的顶点数，显然是 \(2^d\)。于是 \(d\) 维前缀和的暴力算法就是 \(\mathrm O\!\left(2^dn^d\right)\)。

我们常遇到这样的问题：在 \(2^d\) 的个 bitmask 上有一些数，求每个 bitmask 的子集和。这可以看作一个 \(n=2\) 的高维前缀和问题。按上面说的算法是 \(\mathrm O\!\left(4^d\right)\) 的，由于这里 \(n=2\) 的特殊性，我们可以枚举子集做到 \(\mathrm O\!\left(3^d\right)\)。是否有更优秀的方法呢？

我们考虑换一种求高维前缀的思路，考虑一维一维的推。先算出在每个位置算出第 \(2\sim d\) 维固定，第 \(1\) 维的前缀和；再算出第 \(3\sim d\) 维固定，第 \(1\sim 2\) 维的前缀和，这个显然是前面那个一维前缀和的前缀和；以此类推，最后可以求出 \(d\) 维前缀和。脑子里面可以脑补一下这个 gif。所以复杂度是 \(\mathrm O\!\left(dn^d\right)\)，\(n=2\) 时就是 \(\mathrm O\!\left(2^dd\right)\)。

然后众所周知前缀和的逆运算为差分，考虑如何计算高维差分（不知道这个东西有没有用）？只需要一维一维算差分即可，这个可能没有什么好理解的数学证明方法，但你可以从高维往低维再对它做高维前缀和运算，发现正好抵消掉了，而高维前缀和显然是维度顺序无关的。

但是不知道有没有 \(\mathrm O(d)\) 查超立方和或者 \(\mathrm O(d)\) 超立方加？可能没有，可能有，有的话肯定也不属于高维前缀和的范畴了。