算法 —— 前缀和

目录

【模板】一维前缀和

【模板】二维前缀和

寻找数组的中心下标

除⾃⾝以外数组的乘积

矩阵区域和

【模板】一维前缀和

如果我们用暴力解法，每次都要遍历一遍数组，一共遍历q次，这样时间复杂度太高，这时候我们构造一个前缀和数组，将1 - n区间内各区间的和存入进去，需要前n项和直接访问dp前缀和数组的下标位置即可。代码如下：

#include
#include
using namespace std;
int main()
{
	// 读入数据
	int n, q; cin >> n >> q;
	// n + 1 添加了虚拟节点0
	vector arr(n + 1); // 默认全部为0
	for (int i = 1; i > arr[i];
	// 预处理出一个前缀和数组
	vector dp(n + 1); // 防止溢出
	for (int i = 1; i > l >> r;
		cout  n >> m >> q;
	vector arr(n + 1, vector(m + 1));
	for (int i = 1; i  arr[i][j];
	// 预处理一个前缀和数组
	vector dp(n + 1, vector(m + 1)); // 防止溢出
	for (int i = 1; i  x1 >> y1 >> x2 >> y2;
		cout = 0; i--)
			g[i] = g[i + 1] * nums[i + 1];
		for (int i = 0; i  
矩阵区域和
 
 
 
 注意：二维前缀和数组要多开一行一列，否则会产生越界访问，此外dp数组和ans数组之间需要调整下标才能匹配位置，ans[ 0 ][ 0 ]对应的是dp [ 1 ][ 1 ]这个位置。代码如下：
 
class Solution {
public:
	vector matrixBlockSum(vector& mat, int k) {
		int m = mat.size(), n = mat[0].size();  // m 为行 n 为列
		// 预处理一个二维前缀和数组 dp
		vector dp(m + 1, vector(n + 1));
		for (int i = 1; i