二维前缀和

众所周知，二维前缀和可以使用容斥做法。

然而还有另一种巧妙的做法：

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) s[i][j] += s[i - 1][j];
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) s[i][j] += s[i][j - 1];

也就是先竖着转移，再横着转移。

高维前缀和

适用于求解 $\sum \limits _{j \in i} a_j$，当然求和运算可以修改为 $\max , \min$ 之类其他运算。

常使用二进制压缩进行优化转移：

这里维数为 $n$ 的超立方体满足边长都为 $2$。

for (int i = 0; i < n; i++) //维数
    for (int j = 0; j < (1 << n); j++) {
        if ((j >> i) & 1) f[j] += f[j ^ (1 << i)];
    }

时间复杂度为 $O(n \times 2^n)$