最近开始重新刷题，从链表开始。第一部分是前缀和。分为一维数组前缀和和高维数组前缀和。（abandon…）
前缀和数组是牺牲空间换时间的方法，为了解决频繁访问数组某区间的问题，先构造出从开始到当前位置的元素的和，储存在前缀和数组中。查询的时候直接查询前缀和数组，就能把时间复杂度降到O(1)。
大概就是在调用构造函数的时候就额外构造一个这么个数组，查的时候直接从前缀和数组中返回值。这里因为数组是直接内存访问，所以快！
力扣303和304两个题都是前缀和数组可以解的题。
303 区域和检索 - 数组不可变
原题链接
题目原文：
给定一个整数数组nums，处理以下类型的多个查询：
- 计算索引
left和right（包含left和right)之间的nums元素的和，其中left<=right
实现NumArray类：
-
NumArray(int[] nums)使用数组nums初始化对象
-
int sumRange(int i, int j)返回数组nums中索引left和right之间的元素的总和，包含left和right两点
|ू･ω･` )
一维数组的前缀和无可厚非，下标对应起来：
preSum[i] = nums[0] + … + nums[i];
preSum[0] = nums[0];
class NumArray {
private:
vector<int> preSum;
vector<int> nums;
int len;
public:
NumArray(vector<int>& nums) {
this->len = nums.size();
this->nums = nums;
this->preSum.resize(len + 1);
preSum[0] = 0;
for(int i = 1; i <= len; i++) preSum[i] = nums[i - 1] + preSum[i - 1];
}
int sumRange(int left, int right) {
if(left < 0 || right >= len || left >= len) return -1;
return this->preSum[right + 1] - preSum[left];
}
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray* obj = new NumArray(nums);
* int param_1 = obj->sumRange(left,right);
*/
304 二维区域和检索 - 矩阵不可变
一样的思路：
preSum[i][j] = nums[0][0] + … + nums[0][j] + … + nums[i][j];
简化计算：就是求相交的几个四边形面积的小学计算题：
preSum[i][j] = nums[i][j] + preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1];
边缘情况：
第一列：preSum[i][j] = nums[i][j] + preSum[i - 1][j];
第一行：preSum[i][j] = nums[i][j] + preSum[i][j - 1];
/*
* 1 2
* 3 4
*
* 和 = 4 + 1 - 2 - 3
*/
class NumMatrix {
private:
vector<vector<int>> preSum;
vector<vector<int>> matrix;
int row; // 行数
int col; // 列数
void output(vector<vector<int>> &m) {
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) cout << m[i][j] << " ";
cout << endl;
}
}
public:
NumMatrix(vector<vector<int>>& matrix) {
this->matrix = matrix;
this->row = matrix.size();
this->col = matrix[0].size();
this->preSum.resize(row);
for(int i = 0; i < row; i++) preSum[i].resize(col);
/*
output(this->matrix);
cout << endl;
output(this->preSum);
*/
// 和数组
for(int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if(i == 0 && j == 0) preSum[i][j] = matrix[i][j];
else if(i == 0 && j != 0) preSum[i][j] = matrix[i][j] + preSum[i][j - 1];
else if(i != 0 && j == 0) preSum[i][j] = matrix[i][j] + preSum[i - 1][j];
else if(i != 0 && j != 0) preSum[i][j] = matrix[i][j] + preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1];
}
}
/*
cout << endl;
output(this->preSum);
*/
}
int sumRegion(int row1, int col1, int row2, int col2) {
if(row1 < 0 || row2 < 0 || col1 < 0 || col2 < 0 || row1 >= row || row2 >= row || col1 >= col || col2 >= col) return -1;
if(row1 == 0 && col1 == 0) return preSum[row2][col2];
else if(row1 == 0 && col1 != 0) return preSum[row2][col2] - preSum[row2][col1 - 1];
else if(row1 != 0 && col1 == 0) return preSum[row2][col2] - preSum[row1 - 1][col2];
else return preSum[row2][col2] + preSum[row1 - 1][col1 - 1] - preSum[row1 - 1][col2] - preSum[row2][col1 - 1];
}
};
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix* obj = new NumMatrix(matrix);
* int param_1 = obj->sumRegion(row1,col1,row2,col2);
*/
