基本算法——前缀和

AcWing795 前缀和
AcWing796 二维矩阵的和

一维前缀和

前缀和的概念：

题目：

输入一个长度为n的整数序列。
接下来再输入m个询问，每个询问输入一对l, r。
对于每个询问，输出原序列中从第l个数到第r个数的和。

题解

看到求区间和、就可以用到前缀和
思路：前缀和数组的构建，利用前缀和性质快速求解区间和

所以解题的步骤一般就两部

1. 前缀和数组的初始化 s[i] = s[i-1] + a[i]
2. 求解区间和

模板

// 1 维
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

---

二维前缀和

一维前缀和是很好理解的、让我们加深、如果放到二维的情况呢？
同理，我们利用一个矩阵存储前缀和，利用这个前缀和我们可以快速求解子矩阵的和

那么怎么快速求解呢？，让我们看下面的图片

ok，有了这个我们就知道怎么去初始化前缀和和利用前缀和来求解了

题目

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

题解

模板

// 2 维
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j];
S[i, j] = 第i行j列格子左上部分所有元素的和
(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

前缀和的关键就在于如何生成前缀和和如何利用前缀和求解
记住公式即可，如果记不住就画一个图，尤其是二维的，用格子图是很好理解的