前缀和

什么是前缀和

前缀和是一种预处理技术，通过计算数组的前缀和数组，可以在常数时间内快速计算任意子数组的和。前缀和数组 prefix 定义为：
$prefix[i] = \sum_{j=0}^{i} arr[j]$

一维前缀和

对于一个一维数组 arr，前缀和数组 prefix 的计算方法如下：

vector<int> prefix(n + 1, 0);
for (int i = 1; i <= n; ++i) {
    prefix[i] = prefix[i - 1] + arr[i - 1];
}

这样可以轻松计算从arr[l]到arr[r]的和，即prefix[r]-prefix[l-1]

二维前缀和

对于一个二维数组 arr，前缀和数组 prefix 的计算方法如下：

vector<vector<int>> prefix(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        prefix[i][j] = arr[i - 1][j - 1] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
    }
}

通过前缀和数组，可以快速计算任意子矩阵 [x1, y1] 到 [x2, y2] 的和：
sum(x1,y1,x2,y2)=prefix[x2][y2]−prefix[x1−1][y2]−prefix[x2][y1−1]+prefix[x1−1][y1−1]

前缀和的应用

• 子数组和
• 子矩阵和
• 区间查询