奇技淫巧 - 前缀和

前缀和

今天写一则关于 前缀和 和 差分 的博客，主要根据 洛谷题集 学习，不得不说每道题目都各有千秋，即使是 普及 还是 普及- 都有自己的坑，专门坑像我这种“little white”。

首先，该组题中前缀和有两种，一种是一维的，一种是二维的。当然，维度也可以一直增加，但是计算的方法会有变化。

差分 一维前缀和情况

前缀和经常和 差分 一起出现。那么 差分 是什么呢？请先考虑一个问题：

一个序列，最开始全是 0,每次区间加 1 ,最后输出每个数。

如果没有学过差分，你会怎么做，把这个区间所有的都加1，复杂度 O(n)。但是学了差分，假设我们现在要给 [ 2 , 5 ] [2,5] [2,5] 这个区间加一。原来的序列是：

0 0 0 0 0 0 0 0

这时候我们在 2 上面打 +1 标记， 6 上面打 -1 标记。那么现在的序列是：

0 +1 0 0 0 -1 0

有什么用呢？从左往右扫描这个数组，记录当前经过的标签之和，这个和就是对应那个数的答案。这样，对于每个区间加操作，只需要O(1) 的时间打上标记，最后扫描输出即可。

二维前缀和

举个例题来解释：

P3397 地毯 题目背景

此题约为NOIP提高组Day2T1难度。

题目描述

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

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

输入格式

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

接下来 m m m 行，每行两个坐标 ( x 1 , y 1 ) (x_1,y_1) (x1​,y1​) 和 ( x 2 , y 2 ) (x_2,y_2) (x2​,y2​)，代表一块地毯，左上角是 ( x 1 , y 1 ) (x_1,y_1) (x1​,y1​)，右下角是 ( x 2 , y 2 ) (x_2,y_2) (x2​,y2​)。

输出格式

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

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

样例 #1 样例输入 #1

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	0 0 0	0 0 0	0 0 0
0 0 0	1 1 1	1 1 1	0 0 0	0 0 0
0 0 0	1 1 1	1 1 1	0 0 0	0 0 0
0 0 0	0 0 0	0 0 0	0 0 0	0 0 0
0 0 0	0 0 0	0 0 0	0 0 0	0 0 0

覆盖第一、二个地毯后：

0 0 0	0 0 0	0 0 0	0 0 0	0 0 0
0 0 0	1 1 1	1 1 1	0 0 0	0 0 0
0 0 0	1 1 1	2 2 2	1 1 1	1 1 1
0 0 0	0 0 0	1 1 1	1 1 1	1 1 1
0 0 0	0 0 0	1 1 1	1 1 1	1 1 1

覆盖所有地毯后：

0 0 0	1 1 1	1 1 1	1 1 1	0 0 0
0 0 0	1 1 1	1 1 1	0 0 0	0 0 0
0 0 0	1 1 1	2 2 2	1 1 1	1 1 1
0 0 0	0 0 0	1 1 1	1 1 1	1 1 1
0 0 0	0 0 0	1 1 1	1 1 1	1 1 1

---

数据范围

对于 20 % 20% 20% 的数据，有 n ≤ 50 nle 50 n≤50， m ≤ 100 mle 100 m≤100。

对于 100 % 100% 100% 的数据，有 n , m ≤ 1000 n,mle 1000 n,m≤1000。

题解

现在把一维差分拓展到二维。假设我们要覆盖 $[(2,2),(5,5)] $ ，那么标记便可以这样打：

0 0 0 0 0 0
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 0 0 0 0 0

即在每一行都按照一维的方式来操作。

代码实现

#include
using namespace std;
int mapp[2000][2000];

inline int read() //我喜欢快读
{
	int num = 0;
	char c;
	bool flag = false;
	while ((c = getchar()) == ' ' || c == 'n' || c == 'r');
	if (c == '-') flag = true;
	else
		num = c - '0';
	while (isdigit(c = getchar()))
		num = num * 10 + c - '0';
	return (flag ? -1 : 1) * num;
}

int main()
{
	int n=read(),m=read();

	for(int i=0; i
		int x1=read(),y1=read(),x2=read(),y2=read();
		for(int j=x1; j<=x2; j++)
		{
			mapp[j][y1]++;
			mapp[j][y2+1]--;
		}
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			mapp[i][j]=mapp[i][j-1]+mapp[i][j];
			printf("%d ",mapp[i][j]);
		}
		printf("n");
	}
	return 0;
}

带有 max 的前缀和

这类题目，一般都是求 一组数中最大的子段。

以一维数组为例，如果暴力的做法，通常需要 O(n^2)，通常 tle 。这时，就可以通过前缀和计算。思路是：计算到一维数组 a a a 中到 a [ n ] a[n] a[n] 的最大子串（包含 a [ i ] a[i] a[i] ），这样就会有 n个最大值，分别是到 a [ 1 ] a[1] a[1] 、 a [ 2 ] a[2] a[2] … a [ n ] a[n] a[n] 的最大值，然后在找出这些最大值中的最大值，就是最大的子串。

接下来以例题讲解。

P1115 最大子段和 题目描述

给出一个长度为 n n n 的序列 a a a，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 n n n。

第二行有 n n n 个整数，第 i i i 个整数表示序列的第 i i i 个数字 a i a_i ai​。

输出格式

输出一行一个整数表示答案。

样例 #1 样例输入 #1

7
2 -4 3 -1 2 -4 3

样例输出 #1

4

提示 样例 1 解释

选取 [ 3 , 5 ] [3, 5] [3,5] 子段 { 3 , − 1 , 2 } {3, -1, 2} {3,−1,2}，其和为 4 4 4。

数据规模与约定

• 对于 40 % 40% 40% 的数据，保证 n ≤ 2 × 1 0 3 n leq 2 times 10^3 n≤2×103。
• 对于 100 % 100% 100% 的数据，保证 1 ≤ n ≤ 2 × 1 0 5 1 leq n leq 2 times 10^5 1≤n≤2×105， − 1 0 4 ≤ a i ≤ 1 0 4 -10^4 leq a_i leq 10^4 −104≤ai​≤104。

题解

思路如前。

代码实现

#include
using namespace std;
const int MAXN=1e5+5;

inline int read() //我喜欢快读
{
	int num = 0;
	char c;
	bool flag = false;
	while ((c = getchar()) == ' ' || c == 'n' || c == 'r');
	if (c == '-') flag = true;
	else
		num = c - '0';
	while (isdigit(c = getchar()))
		num = num * 10 + c - '0';
	return (flag ? -1 : 1) * num;
}

int main()
{
    int n[200001],p,ans[200001]={0};
    int sum=-9999999;//|x|<=10000   QWQ
    p=read();
    for(int i=1;i<=p;i++)
    {
        n[i]=read();//输入
        ans[i]=max(ans[i-1]+n[i],n[i]);//DP
        sum=max(sum,ans[i]);//取最大值也同时进行，节约时间
    }
    cout< 
二维前缀和 
二维的需要稍稍理解一下。
 
下面我们讲一下什么是二维前缀和，建立在一维前缀和之上，我们要求一个矩阵内一个任意的子矩阵的数的和，我们就可以用二维前缀和，我们还是用DP来预处理，状态和一维前缀和差不多，只不过我们多加了一维。
 
用 
    
     
      
       
        f
       
       
        (
       
       
        i
       
       
        ,
       
       
        j
       
       
        )
       
      
      
       f(i,j)
      
     
    f(i,j) 表示 1,1 这个点与 
    
     
      
       
        (
       
       
        i
       
       
        ,
       
       
        j
       
       
        )
       
      
      
       (i,j)
      
     
    (i,j) 这个点两个点分别为左上角和右下角所组成的矩阵内的数的和，则状态转移方程为：
 
     
      
       
        
         f
        
        
         (
        
        
         i
        
        
         ,
        
        
         j
        
        
         )
        
        
         =
        
        
         f
        
        
         (
        
        
         i
        
        
         ,
        
        
         j
        
        
         −
        
        
         1
        
        
         )
        
        
         +
        
        
         f
        
        
         (
        
        
         i
        
        
         −
        
        
         1
        
        
         ,
        
        
         j
        
        
         )
        
        
         −
        
        
         f
        
        
         (
        
        
         i
        
        
         −
        
        
         1
        
        
         ,
        
        
         j
        
        
         −
        
        
         1
        
        
         )
        
        
         +
        
        
         v
        
        
         a
        
        
         
          l
         
         
          
           i
          
          
           ,
          
          
           j
          
         
        
       
       
         f(i,j)=f(i,j-1)+f(i-1,j)-f(i-1,j-1)+val_{i,j} 
       
      
     f(i,j)=f(i,j−1)+f(i−1,j)−f(i−1,j−1)+vali,j​
 其中 
    
     
      
       
        v
       
       
        a
       
       
        
         l
        
        
         
          i
         
         
          ,
         
         
          j
         
        
       
      
      
       val_{i,j}
      
     
    vali,j​ 表示 
    
     
      
       
        (
       
       
        i
       
       
        ,
       
       
        j
       
       
        )
       
      
      
       (i,j)
      
     
    (i,j) 这一格的价值。
 
怎么来的呢？我们画一下图就知道了。
 
 
一开始是这样的：
    
     
      
       
        f
       
       
        (
       
       
        i
       
       
        ,
       
       
        j
       
       
        )
       
      
      
       f(i,j)
      
     
    f(i,j)为 
    
     
      
       
        0
       
      
      
       0
      
     
    0，即图中所有格子都是白色的。
 
 
回顾转移方程：
    
     
      
       
        f
       
       
        (
       
       
        i
       
       
        ,
       
       
        j
       
       
        )
       
       
        =
       
       
        f
       
       
        (
       
       
        i
       
       
        ,
       
       
        j
       
       
        −
       
       
        1
       
       
        )
       
       
        +
       
       
        f
       
       
        (
       
       
        i
       
       
        −
       
       
        1
       
       
        ,
       
       
        j
       
       
        )
       
       
        −
       
       
        f
       
       
        (
       
       
        i
       
       
        −
       
       
        1
       
       
        ,
       
       
        j
       
       
        −
       
       
        1
       
       
        )
       
       
        +
       
       
        v
       
       
        a
       
       
        
         l
        
        
         
          i
         
         
          ,
         
         
          j
         
        
       
      
      
       f(i,j)=f(i,j-1)+f(i-1,j)-f(i-1,j-1)+val_{i,j}
      
     
    f(i,j)=f(i,j−1)+f(i−1,j)−f(i−1,j−1)+vali,j​
 
第一个加的是 
    
     
      
       
        f
       
       
        (
       
       
        i
       
       
        ,
       
       
        j
       
       
        −
       
       
        1
       
       
        )
       
      
      
       f(i,j-1)
      
     
    f(i,j−1)，所以我们将 
    
     
      
       
        (
       
       
        1
       
       
        ,
       
       
        1
       
       
        )
       
      
      
       (1,1)
      
     
    (1,1) ~ 
    
     
      
       
        (
       
       
        i
       
       
        ,
       
       
        j
       
       
        −
       
       
        1
       
       
        )
       
      
      
       (i,j-1)
      
     
    (i,j−1) 染成黄色，表示加过一次。如上图所示。
 
 
此后再加上 
    
     
      
       
        f
       
       
        (
       
       
        i
       
       
        −
       
       
        1
       
       
        ,
       
       
        j
       
       
        )
       
      
      
       f(i-1,j)
      
     
    f(i−1,j)，但是我们发现两次染色中有一部分是重复染色的。即：
    
     
      
       
        (
       
       
        1
       
       
        ,
       
       
        1
       
       
        )
       
      
      
       (1,1)
      
     
    (1,1)~
    
     
      
       
        (
       
       
        i
       
       
        −
       
       
        1
       
       
        ,
       
       
        j
       
       
        −
       
       
        1
       
       
        )
       
      
      
       (i-1,j-1)
      
     
    (i−1,j−1)，它们被染过两次色，在上图中我们将这一块区域染成棕色。
 
 
既然重复计算了，那我们就剪掉，即减去
    
     
      
       
        f
       
       
        (
       
       
        i
       
       
        −
       
       
        1
       
       
        ,
       
       
        j
       
       
        −
       
       
        1
       
       
        )
       
      
      
       f(i-1,j-1)
      
     
    f(i−1,j−1)，此时 
    
     
      
       
        (
       
       
        1
       
       
        ,
       
       
        1
       
       
        )
       
      
      
       (1,1)
      
     
    (1,1)~
    
     
      
       
        (
       
       
        i
       
       
        −
       
       
        1
       
       
        ,
       
       
        j
       
       
        −
       
       
        1
       
       
        )
       
      
      
       (i-1,j-1)
      
     
    (i−1,j−1) 又回归了黄色（即只染过一次色）。我们发现：只需再把 
    
     
      
       
        (
       
       
        i
       
       
        ,
       
       
        j
       
       
        )
       
      
      
       (i,j)
      
     
    (i,j)这一格染成黄色，便大功告成了！
 
即加上：
    
     
      
       
        v
       
       
        a
       
       
        
         l
        
        
         
          i
         
         
          ,
         
         
          j
         
        
       
      
      
       val_{i,j}
      
     
    vali,j​，如下图：
 
 
所以我们用图解证明了转移方程 
    
     
      
       
        f
       
       
        (
       
       
        i
       
       
        ,
       
       
        j
       
       
        )
       
       
        =
       
       
        f
       
       
        (
       
       
        i
       
       
        ,
       
       
        j
       
       
        −
       
       
        1
       
       
        )
       
       
        +
       
       
        f
       
       
        (
       
       
        i
       
       
        −
       
       
        1
       
       
        ,
       
       
        j
       
       
        )
       
       
        −
       
       
        f
       
       
        (
       
       
        i
       
       
        −
       
       
        1
       
       
        ,
       
       
        j
       
       
        −
       
       
        1
       
       
        )
       
       
        +
       
       
        v
       
       
        a
       
       
        
         l
        
        
         
          i
         
         
          ,
         
         
          j
         
        
       
      
      
       f(i,j)=f(i,j-1)+f(i-1,j)-f(i-1,j-1)+val_{i,j}
      
     
    f(i,j)=f(i,j−1)+f(i−1,j)−f(i−1,j−1)+vali,j​
 
我们看一下实现代码：
 
for(int i=1; i<=m; i++)
    for(int j=1; j<=n; j++)
        f[i][j]=val[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1];
 
现在只需枚举左上角，根据边长 cc 算出左下角，然后用二维前缀和 O(1)O(1) 更新。
 
附 
    
     
      
       
        (
       
       
        
         x
        
        
         1
        
       
       
        ,
       
       
        
         y
        
        
         1
        
       
       
        )
       
      
      
       (x_1,y_1)
      
     
    (x1​,y1​) 到 
    
     
      
       
        (
       
       
        
         x
        
        
         2
        
       
       
        ,
       
       
        
         y
        
        
         2
        
       
       
        )
       
      
      
       (x_2,y_2)
      
     
    (x2​,y2​)权值和的计算方法：
 
     
      
       
        
         f
        
        
         (
        
        
         
          x
         
         
          2
         
        
        
         ,
        
        
         
          y
         
         
          2
         
        
        
         )
        
        
         −
        
        
         f
        
        
         (
        
        
         
          x
         
         
          2
         
        
        
         ,
        
        
         
          y
         
         
          1
         
        
        
         −
        
        
         1
        
        
         )
        
        
         −
        
        
         f
        
        
         (
        
        
         
          x
         
         
          1
         
        
        
         −
        
        
         1
        
        
         ,
        
        
         
          y
         
         
          2
         
        
        
         )
        
        
         +
        
        
         f
        
        
         (
        
        
         
          x
         
         
          1
         
        
        
         −
        
        
         1
        
        
         ,
        
        
         
          y
         
         
          1
         
        
        
         −
        
        
         1
        
        
         )
        
       
       
         f(x_2,y_2)-f(x_2,y_1-1)-f(x_1-1,y_2)+f(x_1-1,y_1-1) 
       
      
     f(x2​,y2​)−f(x2​,y1​−1)−f(x1​−1,y2​)+f(x1​−1,y1​−1)
 下面讲一个例子：
 
P2004 领地选择 
题目描述 
作为在虚拟世界里统帅千军万马的领袖，小 Z 认为天时、地利、人和三者是缺一不可的，所以，谨慎地选择首都的位置对于小 Z 来说是非常重要的。
 
首都被认为是一个占地 
    
     
      
       
        C
       
       
        ×
       
       
        C
       
      
      
       Ctimes C
      
     
    C×C 的正方形。小 Z 希望你寻找到一个合适的位置，使得首都所占领的位置的土地价值和最高。
 
输入格式 
第一行三个整数 
    
     
      
       
        N
       
       
        ,
       
       
        M
       
       
        ,
       
       
        C
       
      
      
       N,M,C
      
     
    N,M,C，表示地图的宽和长以及首都的边长。
 
接下来 
    
     
      
       
        N
       
      
      
       N
      
     
    N 行每行 
    
     
      
       
        M
       
      
      
       M
      
     
    M 个整数，表示了地图上每个地块的价值。价值可能为负数。
 
输出格式 
一行两个整数 
    
     
      
       
        X
       
       
        ,
       
       
        Y
       
      
      
       X,Y
      
     
    X,Y，表示首都左上角的坐标。
 
样例 #1 
样例输入 #1 
3 4 2
1 2 3 1
-1 9 0 2
2 0 1 1
 
样例输出 #1 
1 2
 
提示 
对于 
    
     
      
       
        60
       
       
        %
       
      
      
       60%
      
     
    60% 的数据，
    
     
      
       
        N
       
       
        ,
       
       
        M
       
       
        ≤
       
       
        50
       
      
      
       N,Mle 50
      
     
    N,M≤50。
 
对于 
    
     
      
       
        90
       
       
        %
       
      
      
       90%
      
     
    90% 的数据，
    
     
      
       
        N
       
       
        ,
       
       
        M
       
       
        ≤
       
       
        300
       
      
      
       N,Mle 300
      
     
    N,M≤300。
 
对于 
    
     
      
       
        100
       
       
        %
       
      
      
       100%
      
     
    100% 的数据，
    
     
      
       
        1
       
       
        ≤
       
       
        N
       
       
        ,
       
       
        M
       
       
        ≤
       
       
        1
       
       
        
         0
        
        
         3
        
       
      
      
       1le N,Mle 10^3
      
     
    1≤N,M≤103，
    
     
      
       
        1
       
       
        ≤
       
       
        C
       
       
        ≤
       
       
        min
       
       
        ⁡
       
       
        (
       
       
        N
       
       
        ,
       
       
        M
       
       
        )
       
      
      
       1le Cle min(N,M)
      
     
    1≤C≤min(N,M)。
 
代码实现 
#include
using namespace std;
int mapp[1005][1005];

inline int read() //我喜欢快读
{
	int num = 0;
	char c;
	bool flag = false;
	while ((c = getchar()) == ' ' || c == 'n' || c == 'r');
	if (c == '-') flag = true;
	else
		num = c - '0';
	while (isdigit(c = getchar()))
		num = num * 10 + c - '0';
	return (flag ? -1 : 1) * num;
}

int main()
{
	int n=read(),m=read(),c=read();
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			mapp[i][j]=read()+mapp[i-1][j]+mapp[i][j-1]-mapp[i-1][j-1];
		}
	}
//	for(int i=1; i<=n; i++)
//	{
//		for(int j=1; j<=m; j++)
//		{
//			cout<
		for(int j=1; j<=m-c+1; j++)
		{
			if(mapp[i+c-1][j+c-1]-mapp[i-1][j+c-1]-mapp[i+c-1][j-1]+mapp[i-1][j-1]>maxx)
			{
				x=i;
				y=j;
				maxx=mapp[i+c-1][j+c-1]-mapp[i-1][j+c-1]-mapp[i+c-1][j-1]+mapp[i-1][j-1];
			}
		}
	}
	cout< 
这道题的坑点是，maxx=-0x7fffffff，一定要设置的小。
 
其他的一些二维前缀和的注意点，就是你在写面积的时候， maxx=mapp[i+c-1][j+c-1]-mapp[i-1][j+c-1]-mapp[i+c-1][j-1]+mapp[i-1][j-1]这种最后坐标 +1 还是 -1 需要思考一下。
 
其他的大家可以做一下洛谷题集，好好思索！