前缀和的理解

前缀和的理解

前缀和：指某序列的前n项和，可以把它理解为数学上的数列的前n项和。

一维前缀和：

假设原数组为 arr[] , 定义一个 sum[] 数组，sum[i] 代表 arr 数组中前 i 个数的和。即：sum[i] = sum[i − 1] + arr[i]，若查询 [l,r] 的和，只需计算ans=sum[r]−sum[l−1]。

int get_sum(int L, int R){
	if(L != 0){
		return sum[R] - sum[L - 1];
	}
	else return{
		sum[R];
	}
}  

二维前缀和：

输入一个m行n列的整数矩阵，再输入k个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。定义一个二维数组sum[][], sum[i][j]表示二维数组中，左上角(1,1)到右下角( i,j )所包围的矩阵元素的和，只需计算

ans = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]。

int sum[n][m];
void pre_sum(){
	sum[0][0] = g[0][0]; 
	for(int i = 1; i < n; i++){
		sum[i][0] = sum[i - 1][0] + g[i][0];
		}//第一列
	for(int j = 1; j < m; j++){
		sum[0][j] = sum[0][j - 1] + g[0][j];
		}//第一行
	for(int i = 1; i < n; i++){
		for(int j = 1; j < m; j++){
			sum[i][j] = g[i][j] + sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j- 1];
		}
	}
}

同时需要注意：

1.左上角为0，0

if (!x1 && !y1){
		return sum[x2][y2];
		}

2.左上角的行为0,抽象成为多行的一维前缀和

	if (!x1){
		return sum[x2][y2] -sum[x2][y1 - 1];
		}

3.左上角的列为0,抽象成为多列的一维前缀和

	if (!y1){
		return sum[x2][y2] - sum[x1 - 1][y2];
		}