前缀和

一维

一个数组prefix中，第i个元素表示nums[0]至nums[i-1]的总和，那么我们就称这个prefix数组是nums数组的前缀和。
$$\text{prefix}[i]=\sum _{j=0}^i\text{nums}[j]$$

应用

1、快速计算下标为[i , j]区间的和。

• prefix[j+1]- prefix[i]即为下标[i , j]之间元素的总和。

二维

class NumMatrix {vector<vector<int>> sum;
public:NumMatrix(vector<vector<int>> &matrix) {int m = matrix.size(), n = matrix[0].size();sum.resize(m + 1, vector<int>(n + 1));for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + matrix[i][j];}}}// 返回左上角在 (r1,c1) 右下角在 (r2,c2) 的子矩阵元素和int sumRegion(int r1, int c1, int r2, int c2) {return sum[r2 + 1][c2 + 1] - sum[r2 + 1][c1] - sum[r1][c2 + 1] + sum[r1][c1];}
};作者：灵茶山艾府
链接：https://leetcode.cn/problems/range-sum-query-2d-immutable/solutions/2667331/tu-jie-yi-zhang-tu-miao-dong-er-wei-qian-84qp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。