前缀和

路西法，前缀和：不明所以

labuladong👀️

二维前缀和

Lucifer 二维的写得比一维的清晰

• 简单二维前缀和的求解 基于 容斥原理

二维前缀和转化为一维前缀和 （遍历矩阵所有的以第一行为上端的区块和）

先不考虑行之间的关联，而是预先计算出每一行的前缀和。对于计算每一行的前缀和就是一维前缀和啦。接下来通过固定两个列的端点的方式计算每一行的区域和。代码上，我们可以通过三层循环来实现， 其中两层循环用来固定列端点，另一层用于枚举所有行。

# 预先构建行的前缀和
for row in matrix:
    for i in range(n - 1):
        row[i + 1] += row[i]

# 固定列的两个端点，即枚举所有列的组合
for i in range(n):
    for j in range(i, n):
        pres = [0]
        pre = 0
        # 枚举所有行
        for k in range(m):
            # matrix[k] 其实已经是上一步预处理的每一行的前缀和了。因此 matrix[k][j] - (matrix[k][i - 1] 就是每一行 [i, j] 的区域和。
            pre += matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0)
            pres.append(pre)

上面代码做的事情形象来看，就是先在水平方向计算前缀和，然后在竖直方向计算前缀和，而不是同时在两个方向计算。