概述

这节课我们将学习一种非常实用的算法——前缀和，功能和线段树有点类似。

代入问题

给定一个长度为n的序列，q次询问，每次给定l和r，求a[l]+a[l+1]+…+a[r]，即sigema(i = l, r, a[i])。

法1：遍历区间求和

#include <bits/stdc++.h>
using namespace std;
int main() {
          
   
	int n, q;
	cin >> n >> q;
	int *a = new int[n + 1];
	for (int i = 1; i <= n; ++i) {
          
   
		cin >> a[i];
	} 
	while (q--) {
          
   
		int l, r;
		cin >> l >> r;
		long long sum = 0;
		for (int i = l; i <= r; ++i) {
          
   
			sum += a[i];
		}
		cout << sum << 
;
	}
	return 0;
}

分析 暴力枚举，时间复杂度O(nq)（有亿点高），空间复杂度O(n)。

法2：一维前缀和

预处理：O(n)

new一个sum数组，sum[i] = sigema(j = 1, i, a[j])，即数组前i个数的和。 递推公式：sum[i] = sum[i - 1] + a[i] 边界条件：sum[0] = 0

int *a = new int[n + 1];
int *sum = new int[n + 1]; 
for (int i = 1; i <= n; ++i) {
          
   
	cin >> a[i];
	sum[i] = sum[i - 1] + a[i];
}

查询：O(1)

直接输出sum[r] - sum[l - 1]。 证明

while (q--) {
          
   
	int l, r;
	cin >> l >> r;
	cout << sum[r] - sum[l - 1] << 
;
}

全部代码(〃‘▽’〃)~

#include <bits/stdc++.h>
using namespace std;
int main() {
          
   
	int n, q;
	cin >> n >> q;
	int *a = new int[n + 1];
	int *sum = new int[n + 1]; 
	for (int i = 1; i <= n; ++i) {
          
   
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
	} 
	while (q--) {
          
   
		int l, r;
		cin >> l >> r;
		cout << sum[r] - sum[l - 1] << 
;
	}
    return 0;
}

衔接

以上我们学习了简单的一维前缀和，那么有没有二位的呢？ for example，著名的最大加权矩形目前 （除了打表） 最好滴解法就是这个啦

二维前缀和

模板问题

给定n,m以及数组a[n][m]，q与q次询问，每次询问包含x1, y1, x2, y2四个元素，表示访问矩形的左上角坐标与右下角坐标，求矩形内所有数的和。

法1：枚举

直接遍历数组求和。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int a[N][N];
int main() {
          
   
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1; i <= n; ++i) {
          
   
		for (int j = 1; j <= m; ++j) {
          
   
			cin >> a[i][j];
		}
	} 
	while (q--) {
          
   
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		long long sum = 0;
		for (int i = x1; i <= x2; ++i) {
          
   
			for (int j = y1; j <= y1; ++j) {
          
   
				sum += a[i][j];
			}
		}
		cout << sum << 
;
	}
    return 0;
}

分析 时间复杂度：O(n2q) 空间复杂度：O(nm) 经过实测，大部分OJ只有40pts（QAQ）。

法2：二维前缀和

结论

s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i][j] - s[i - 1][j - 1] sigema(i = x1, j = y1, x2, y2, a[i][j]) = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]

证明

公式1 在此图中：

公式2 在此图中：

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N][N], sum[N][N];
int main() {
          
   
	int n, m, q;
	cin >> n >> m >> q;
    for (int i = 1; i <= n; ++i) {
          
   
        for (int j = 1; j <= m; ++j) {
          
   
            cin >> a[i][j];
            s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i][j] - s[i - 1][j - 1];
        }
    }
    while (q--) {
          
   
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
    }
    return 0;
}

练习题目

1. 2. 3. 4. 5. 6.