一维前缀和

https://www.acwing.com/problem/content/797/

#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], s[N];
int main(void)
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        s[i] = s[i - 1] + a[i];
    }
    while (m--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);
    }
    return 0;
}

在了解二维前缀和之前，我们首先需要了解一下什么是前缀和。

如果我给你一串长度为n的数列a1,a2,a3…an,再给出m个询问，每次询问给出L，R两个数，要求给出区间[L,R]里的数的和，你会怎么做，若是没有了解过前缀和的人看到这道题的想法可能是对于m次询问，我每次都遍历一遍它给的区间，计算出答案，这样子的方法固然没错，但是其时间复杂度达到了O(n*m)，如果数据量稍微大一点就有可能超时，而我们如果使用前缀和的方法来做的话就能够将时间复杂度降到O(n+m),大大节省了运算时间。至于怎么用，请看下面一小段代码

for(int i=1;i<=n;i++)
   a[i]+=a[i-1];

前缀和顾名思义就是前面i个数的总和。数组a在经过这样的操作之后，对于每次的询问，我们只需要计算a[R]-a[L-1]就能得到我们想要的答案了，是不是很简单呢。

二维前缀和

求子矩阵的和
输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n，m，q。
接下来 n 行，每行包含 m 个整数，表示整数矩阵。
接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。
输出格式
共 q 行，每行输出一个询问的结果。
数据范围
1≤n,m≤1000 ,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例：
17
27
21

#include<iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], s[N][N];

int main()
{
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1; i <= n; i ++ )
		for(int j = 1; j <= m; j ++ )
			scanf("%d", &a[i][j]);
	
	// 求前缀数组 s
	for(int i = 1; i <= n; i ++ )
		for(int j = 1; j <= m; j ++ )
			s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];

	// q 次询问
	while(q --)
	{
		int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        
        printf("%d\n", (s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]));
	}
		
	return 0;
}

差分

在知道了最简单的前缀和之后，我们再来了解一下什么是差分。

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int d[N],a[N];
int main(void) {
    int n,m;
    cin >> n >> m;
    for(int i = 1;i<=n;i++){
        cin >> a[i];
        d[i] = a[i] - a[i-1];
    }
    for(int i = 1;i<=m;i++){
        int l,r,c;
        cin >> l >> r >> c;
        d[l]+=c;
        d[r+1]-=c;
    }
    for(int i = 1;i<=n;i++){
        d[i]+=d[i-1];
        cout << d[i] << " ";
    }
}

前缀和练习题

1

#include <iostream>
#include <cstdio>
#include <climits>
//https://www.luogu.com.cn/problem/P2004
using namespace std;
const int N = 1e3;
int arr[N][N];
int sum[N][N];
int main() {
	int n,m,c;
	scanf("%d %d %d",&n,&m,&c);
	for(int i = 1;i<=n;i++) {
		for(int j = 1;j<=m;j++) {
			scanf("%d",&arr[i][j]);
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
		}
	}
	int ansX,ansY;
	int maxNum = INT_MIN;
	for(int i = c;i<=n;i++) {
		for(int j = c;j<=m;j++) {
			int res = sum[i][j] - sum[i - c - 1][j] - sum[i][j - c -1] + sum[i - c -1][j - c -1];
			if(res > maxNum) {
				maxNum = res;
				ansX = i - c;
				ansY = j - c;
			}
		}
	}
	printf("%d %d\n",ansX,ansY);
	
} 

差分练习题

1

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int d[N];
int main() {
    int n,m;
    cin >> n >> m;
    for(int i = 1;i<=n;i++) {
        cin >> a[i];
        d[i] = a[i] - a[i - 1];
    }
    for(int i = 0;i<m;i++) {
        int l,r,c;
        cin >> l >> r >> c;
        d[l] += c;
        d[r + 1] -=c;
    }
    for(int i = 1;i<=n;i++){
        a[i] = d[i] + a[i - 1];
        cout << a[i] << " ";
    }
}