前缀和与二维前缀和
考虑一个序列 \(a\)，我们如何快速求出区间 \([l, r]\) 的元素和呢？这很简单，我们只需求出它的前缀和序列 \(\mathrm{sum}(i) = \sum_{k = 1}^i a_i\)，那么答案即为 \(\mathrm{sum}(r) - \mathrm{sum}(l - 1)\)。而对于序列 \(\mathrm{sum}\)，有 \(\mathrm{sum}(i) = \mathrm{sum}(i - 1) + a_i\)，可以在 \(\Theta(n)\) 时间内递推求出。因此借助前缀和，我们即可做到 \(\Theta(n)\) 预处理、\(\Theta(1)\) 查询。
进一步地，考虑把这个问题扩展到二维。对于一个矩阵 \(a\)，我们如何快速求出行坐标为 \([l_1, r_1]\)、列坐标为 \([l_2, r_2]\) 的子矩阵中所有元素的和呢？这也不难，我们记一个类似的前缀和矩阵 \(\mathrm{sum}(i, j)\)，表示行坐标为 \([1, i]\)、列坐标为 \([1, j]\) 的子矩阵中所有元素的和。很自然地，我们考虑容斥，那么答案为 \(\mathrm{sum}(r_1, r_2) - \mathrm{sum}(l_1 - 1, r_2) - \mathrm{sum}(r_1, l_2 - 1) + \mathrm{sum}(l_1 - 1, l_2 - 1)\)。这就是说，借助前缀和矩阵 \(\mathrm{sum}(i, j)\)，我们就可以使用容斥在 \(\Theta(1)\) 的时间复杂度内求出上述问题的答案。
问题转化为如何求出前缀和矩阵 \(\mathrm{sum}(i, j)\)。事实上，对于元素 \(a_{i, j}\)，我们可以将其看作行坐标为 \([i, i]\)、列坐标为 \([j, j]\) 的子矩阵，根据答案的表达式有 \(a_{i, j} = \mathrm{sum}(i, j) - \mathrm{sum}(i - 1, j) - \mathrm{sum}(i, j - 1) + \mathrm{sum}(i - 1, j - 1)\)，因此我们也可以使用类似的容斥得出 \(\mathrm{sum}(i, j) = a_{i, j} + \mathrm{sum}(i - 1, j) + \mathrm{sum}(i, j - 1) - \mathrm{sum}(i - 1, j - 1)\)。即对于矩阵 \(\mathrm{sum}(i, j)\)，我们也可以在 \(\Theta(n^2)\) 时间内递推求出。因此借助前缀和，我们即可做到 \(\Theta(n^2)\) 预处理、\(\Theta(1)\) 查询。
不妨将上面的前缀和矩阵 \(\mathrm{sum}(i, j)\) 看作二维前缀和。我们发现，在处理这类前缀和的过程中，容斥是一个非常实用的工具。
容斥原理
对于一个 \(n\) 维的数组 \(a(i_1, i_2, i_3, \cdots, i_n)\)，设每一维的值域均为 \([1, m]\)。我们定义其前缀和数组 \(\mathrm{sum}(i_1, i_2, i_3, \cdots, i_n)\) 表示所有满足 \(1 \leq j_1 \leq i_1, 1 \leq j_2 \leq i_2, 1 \leq j_3 \leq i_3, \cdots, 1 \leq j_n \leq i_n\) 的元素 \(a(j_1, j_2, j_3, \cdots, j_n)\) 的和。那么问题来了：如何才能快速求出 \(\mathrm{sum}\) 数组中每个元素的值？
显然有一个 \(\Theta((m ^ n)^ 2) = \Theta(m ^ {2n})\) 的暴力：我们枚举每一对 \((i_1, i_2, \cdots, i_n), (j_1, j_2, \cdots, j_n)\)，判断是否满足 \(j_1 \leq i_1, j_2 \leq i_2, \cdots, j_n \leq i_n\)，若满足，则将 \(a(j_1, j_2, \cdots, j_n)\) 累加到 \(a(i_1, i_2, \cdots, i_n)\) 中。显然这个暴力太不优美了，因为我们发现它枚举了很多无用的状态；那么对于每一个固定的状态 \(i\)，考虑将每一维 \(j_k\) 的枚举范围缩小至 \([1, i_k]\)，即可做到所有枚举的状态都有贡献，这样复杂度即可降至 \(\Theta(\Theta(\frac{m ^ {2n}}{2 ^ n})\)。
然而我们发现复杂度仍然不够优秀，因为相对于 \(\Theta(m ^ n)\) 的输入量，它还是平方级别的。此时，让我们回顾一下开头提到的二维前缀和是怎么做的：首先，对于状态 \(a(i_1, i_2)\) 它的暴力也是枚举 \(j_1 \in [1, i_1], j_2 \in [1, i_2]\)，然后累加贡献，和这个问题很类似（事实上它就是该问题的一个特例）；其次，我们发现它巧妙地应用了前缀和数组 \(\mathrm{sum}\) 本身，将其转化为了一个容斥问题 \(\mathrm{sum}(i_1, i_2) = a(i_1, i_2) + \mathrm{sum}(i_1 - 1, i_2) + \mathrm{sum}(i_1, i_2 - 1) - \mathrm{sum}(i_1 - 1, i_2 - 1)\)，于是每个状态 \(\mathrm{sum}(i_1, i_2)\) 都可以在 \(\Theta(1)\) 的复杂度内地推求出。
于是在求高维前缀和的过程中，我们考虑将上面的容斥套过来。此时你已知 \(a(i_1, i_2, \cdots, i_n)\) 的值；对于其他需要累加的值，我们考虑从 \(\mathrm{sum}\) 数组中前面的状态转移过来，且状态每一维 \(j_k\) 均为 \(i_k\) 或 \(i_k - 1\)。考虑对每一个这样的状态 \(\mathrm{sum}(j_1, j_2, \cdots, j_k)\) 计算其容斥系数，记 \(s_k = i_k - j_k\)，那么根据容斥原理，该项的容斥系数为 \((-1)^{s_1 + s_2 + \cdots + s_k + 1}\)。类比二维前缀和理解即可。
\[\mathrm{sum}(i_1, i_2, \cdots, i_n) = a(i_1, i_2, \cdots, i_n) + \sum_{s_1, s_2, \cdots, s_n \in \{ 0, 1 \}} [s_1 + s_2 + \cdots + s_n > 0] (-1)^{s_1 + s_2 + \cdots + s_n + 1} \mathrm{sum}(i_1 - s_1, i_2 - s_2, \cdots, i_n - s_n) \]考虑其时间复杂度。由于每一个状态的求解过程都要依赖于它前面的 \(\Theta(2^n)\) 个状态，因此时间复杂度降至 \(\Theta(m^n \cdot 2^n) = \Theta((2m) ^ n)\)。
然而某些题的数据范围把 \(m^n\) 开到 \(10^6\) 级别，发现这样依然无法通过。怎么办？
高维前缀和
我们回到最简单的问题，考虑一维前缀和是怎么求的：显然有 \(\mathrm{sum}(i) = \mathrm{sum}(i - 1) + a_i\)，因此直接从左往右扫一遍即可。时间复杂度为 \(\Theta(n)\)。
那么二维前缀和怎么求呢？根据一维前缀和，我们可以得到一个比容斥更简单的做法。考虑先把每一行的前缀和数组求出来，记 \(s(i, j) = \sum_{k = 1}^j a_{i, j}\) 表示第 \(i\) 行前 \(j\) 个数的和；稍加思考即可发现，当 \(j\) 固定时，\(\mathrm{sum}(i, j)\) 即为 \(s\) 数组第 \(j\) 列的前缀和，因此有 \(\mathrm{sum}(i, j) = \sum_{k = 1}^i s(i, j)\)。
考虑在线地维护这个过程：初始时，令 \(\mathrm{sum}(i, j) = a(i, j)\)，只表示 \(a(i, j)\) 这一个位置的“和”。我们将求前缀和的过程分为两轮：我们期望在第一轮结束后，\(\mathrm{sum}(i, j)\) 表示第 \(i\) 行的前缀和，那么只需对每一行做一遍一维前缀和即可；期望在第二轮结束后，\(\mathrm{sum}(i, j)\) 表示矩阵的二维前缀和，因此再对每一列做一遍前缀和即可。时间复杂度为 \(\Theta(n^2)\)。
我们也可以用类似的方法求出高维前缀和。具体地，对于一个 \(n\) 维数组 \(a(i_1, i_2, \cdots, i_n)\)，考虑将球前缀和的过程分为 \(n\) 轮；我们希望在第 \(t\) 轮结束后，\(\mathrm{sum}\) 数组表示的含义为：对于第 \(j \in [1, t]\) 维，它表示该维上的前缀和；对于第 \(j \in [t + 1, n]\) 维，它仅表示这一维上的值。即第 \(t\) 轮结束后，前缀和数组 \(\mathrm{sum}\) 表示：
\[\mathrm{sum}(i_1, i_2, \cdots, i_n) = \sum_{j_1, j_2, \cdots, j_n} [1 \leq j_1 \leq i_1] [1 \leq j_2 \leq i_2] \cdots [1 \leq j_t \leq i_t] [j_{t + 1} = i_{t + 1}] [j_{t + 2} = i_{t + 2}] \cdots [j_n = i_n] a(j_1, j_2, \cdots, j_n) \]比较状态的含义可知，从第 \(t - 1\) 轮结束到第 \(t\) 轮结束，我们只需要把第 \(t\) 的含义变成该维上的前缀和。因此只需固定其他维不变，对第 \(t\) 维做一遍一维前缀和即可。同样类比求二维前缀和的过程理解即可。
由于求前缀和的过程有 \(n\) 轮，每一轮我们都需要枚举所有 \(m^n\) 种状态，因此时间复杂度降至 \(\Theta(m^n \cdot n)\)。
注意这种方法只能优化求高维前缀和的过程，如果我们要求它的某个子空间中所有元素的和，还是只能老老实实地使用容斥原理。
子集枚举
定义全集 \(I = \{ 0, 1, \cdots, n - 1 \}\)，我们给它的每一个子集 \(S \subseteq I\) 赋一个权值 \(a_S\)。定义 \(\mathrm{sum}(S)\) 表示所有 \(S\) 的子集的权值和，即 \(\mathrm{sum}(S) = \sum_{T \subseteq S} a_T\)。那么如何快速求出 \(\mathrm{sum}\) 数组呢？
常规的做法是对其进行子集枚举：对的每个状态 \(\mathrm{sum}(S)\)，我们暴力枚举所有 \(S\) 的子集 \(T\)，并累加所有 \(a(T)\) 的值，由二项式定理可知时间复杂度为 \(\Theta(3^n)\)。当然你也可以使用容斥，但我们发现此时容斥和直接暴力所需要枚举的状态数是一样的，甚至容斥实现起来还要复杂一些。
事实上，我们可以将 \(a_S\) 看成一个 \(n\) 维数组 \(a(i_0, i_1, i_2, \cdots, i_{n - 1})\)，其中每一维 \(i_k\) 表示 \(k\) 这个元素在 \(S\) 中是否出现过；那么 \(\mathrm{sum}\) 就相当于是 \(a\) 的前缀和数组。考虑把求高维前缀和的方法套用过来：我们将整个过程分成 \(n\) 轮，第 \(i \in [0, n)\) 轮对第 \(i\) 维求一遍一维前缀和。事实上，这个一维前缀和非常特殊，固定其他维不变时，我们只需要把第 \(i\) 位上值为 \(0\) 的状态累加到值为 \(1\) 的状态上即可。时间复杂度即可优化至 \(\Theta(2^n \cdot n)\)。
这里附上“子集枚举”与“高维前缀和优化”的代码。
代码（子集枚举）
for(i=0;i<(1<<n);i++)
for(j=i;true;j=(j-1)&i){
sum[i]+=a[j];
if(!j) break;
}
代码（高维前缀和优化子集枚举）
for(i=0;i<(1<<n);i++) sum[i]=a[i];
for(i=0;i<n;i++)
for(j=0;j<(1<<n);j++)
if(j>>i&1) sum[j]+=sum[j^(1<<i)];