C++：第九讲前缀和与差分

Everyday English

Your optimal career is simply this: Share the real you with physical world through th e process of creative self-expression.
你的最佳职业很简单，就是这样：通过创造性自我表达的途径和世界分享真实的你。

前言

这节课带你们学习一下怎么优化程序。

前缀和

前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和，而差分可以看成前缀和的逆运算。合理的使用前缀和与差分，可以将某些复杂的问题简单化。

前缀和也指一个数组的某下标之前的所有数组元素的和（包含其自身）。前缀和分为一维前缀和，以及二维前缀和。前缀和是一种重要的预处理，能够降低算法的时间复杂度。可以快速地求出某一段的和。

当然了，前缀和也分为一维前缀和和二维前缀和。

前缀和可以简单理解为「数列的前项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度。

C++ 标准库中实现了前缀和函数，定义于头文件 <numeric> 中。

前缀和的好处

而且前缀和时间复杂度：预处理O(n),查询O(1)，效率比较高效，后续也会有一些其他的解法，比如说线段树，树状数组等，前缀和的运行时间是最短的。

洛谷小课堂P1387最大正方形

题目描述

在一个 n*m的只包含 0 和 1 的矩阵里找出一个不包含 0的最大正方形，输出边长。

输入格式：

输入文件第一行为两个整数 n,m（1<=n,m<=100），接下来 $n$ 行，每行 $m$ 个数字，用空格隔开，0 或 1。

输出格式：

一个整数，最大正方形的边长。

样例输入
4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1

样例输出
2

c++ AC:

#include <algorithm>
#include <iostream>
using namespace std;
int a[103][103];
int b[103][103];  // 前缀和数组，相当于上文的 sum[]
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> a[i][j];
      b[i][j] =
          b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1] + a[i][j];  // 求前缀和
    }
  }
  int ans = 1;
  int l = 2;
  while (l <= min(n, m)) {  // 判断条件
    for (int i = l; i <= n; i++) {
      for (int j = l; j <= m; j++) {
        if (b[i][j] - b[i - l][j] - b[i][j - l] + b[i - l][j - l] == l * l) {
          ans = max(ans, l);  // 在这里统计答案
        }
      }
    }
    l++;
  }
  cout << ans << endl;
  return 0;
}

python AC:

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = [a[0]] + [[i[0]] + [0] * (m - 1) for i in a[1:]]
ans = 0
for i in range(1, n):
    for j in range(1, m):
        if a[i][j]:
            b[i][j] = min(b[i-1][j], b[i][j-1], b[i-1][j-1]) + 1
            ans = max(ans, b[i][j])
print(ans)

差分

当对某些不确定的区间多次进行加减操作时，如果每次都是对这些区间遍历操作，那么时间复杂度是O(nm)。而如果我们采用差分法来求解，就是先构造一个差分数组，然后转化为对区间端点的操作，这样的话时间复杂度就转化为O(n)。

差分的好处

它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。

C++ 标准库中实现了差分函数，定义于头文件 <numeric> 中。

注意：

差分法只能用于区间的加减的运算。

洛谷小课堂P3397 地毯

地毯

题目描述

在 n*n 的格子上有m个地毯。

给出这些地毯的信息，问每个点被多少个地毯覆盖。

输入格式

第一行，两个正整数 n,m。意义如题所述。

接下来 m 行，每行两个坐标 (x_1,y_1) 和 (x_2,y_2)，代表一块地毯，左上角是 (x_1,y_1)，右下角是 (x_2,y_2)。

输出格式

输出n行，每行n个正整数。

第i行第i列的正整数表示 (i,j)这个格子被多少个地毯覆盖。

样例输入
5 3
2 2 3 3
3 3 5 5
1 2 1 4

样例输出 #1
0 1 1 1 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1

提示

样例解释

覆盖第一个地毯后：

0	0	0	0	0
0	1	1	0	0
0	1	1	0	0
0	0	0	0	0
0	0	0	0	0

思路点拨

差分的主要思想其实就是用O(1)复杂度来表示O(N)的覆盖——用B[I]表示A[I]-A[I-1]，所以当覆盖A[L]至A[R]时，只需B[L]++，B[R+1]--即可。最后，再用O(N^2)的复杂度复原A数组，然后输出就行了。

c++AC:

#include<bits/stdc++.h>
using namespace std;
int a[1001][1001],m,n;
int main(){
	cin>>n>>m;
	int b,c,d,e;
	for(int i=1;i<=m;i++){
		cin>>b>>c>>d>>e;
		for(int j=b;j<=d;j++){
			for(int k=c;k<=e;k++){
				a[j][k]++;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}