【编程笔记】前缀和·子矩阵的和

前缀和

输入一个长度为 n 的整数序列。

接下来再输入 m 个询问，每个询问输入一对 l,r。

对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。

输入格式

第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示整数数列。

接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。

输出格式

共 m 行，每行输出一个询问的结果。

前缀和思路

原数组：a[1], a[2],a[3], ... a[n]

前缀和数组：S[i]=a[1]+a[2]+... a[n]

前缀和一定要从下标一开始。这样有利于处理边界问题（这样一来下面用的S[i-1] 不会出现-1的问题，同时令S[0]=0）

S[i]=S[i-1]+a[i]

前缀和数组的作用：快速求出原数组的某一段的和（[l,r]区间,l到r），即[l,r]区间的和为S[r]-S[l-1] 

时间复杂度：O(n)

前缀和的过程

1.初始化原数组

2.初始化前缀和数组

3.查询子矩阵

子矩阵的和

输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式

第一行包含三个整数 n，m，q。

接下来 n 行，每行包含 m 个整数，表示整数矩阵。

接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。

输出格式

共 q 行，每行输出一个询问的结果。

子矩阵的和的思路

子矩阵的和就是二维的前缀和。

那么，S[i,j]和[X1,Y1],[X2,Y2]的矩阵和就是如下的样子。

子矩阵的和的思路主要采用了“容斥原理”的思想，即，先不考虑重叠情况，计算某一内容包含的所有对象的个数，再排除重复计算的个数，使计算结果既不遗漏也不重复。

S[i,j]即为左图蓝色部分中所有数的的和为：

S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j]

(x1,y1),(x2,y2)子矩阵即为右图中蓝色部分中所有数的和为：

S[x2,y2]−S[x1−1,y2]−S[x2,y1−1]+S[x1−1,y1−1]

S[i-1,j-1]是S[i-1,j]和S[i,j-1]两个子矩阵相加得到的重复部分，因此需要消除出去。

S[X1-1,Y1-1]是S[X1-1,Y2]和S[X2,Y1-1]两个子矩阵相加得到的重复部分，因此需要消除出去。

无奈，将就一下，图片在专栏中被自动压缩就看的不太清了。

子矩阵的和的过程

1.初始化原数组

2.初始化前缀和数组

3.查询子矩阵

二维前缀和和一维前缀和的过程相似，差别主要体现在初始化和查询上。

困倦，学一会儿睡觉去了。

夕弦的图片由NovalAI生成。