前缀和
一维前缀和
`
#include <vector>
class Code01_PrefixSumArray {
public:
class NumArray {
public:
std::vector<int> sum;
NumArray(std::vector<int>& nums) {
sum.resize(nums.size() + 1);
for (int i = 1; i <= nums.size(); i++) {
sum[i] = sum[i - 1] + nums[i - 1];
}
}
int sumRange(int left, int right) {
return sum[right + 1] - sum[left];
}
};
};
`
一维差分
等差数列的差分
!
二维
二维前缀和
#include <vector>
class Code01_PrefixSumMatrix {
public:
class NumMatrix {
private:
std::vector<std::vector<int>> sum;
public:
NumMatrix(std::vector<std::vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return;
int n = matrix.size();
int m = matrix[0].size();
sum = std::vector<std::vector<int>>(n + 1, std::vector<int>(m + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
sum[i][j] = matrix[i-1][j-1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
sum[i][j] += sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
}
}
}
int sumRegion(int a, int b, int c, int d) {
return sum[c+1][d+1] - sum[c+1][b] - sum[a][d+1] + sum[a][b];
}
};
};
二维差分
