qijuntong2012's blog

低调做人，高调做事

0%

二维前缀和

发表于 更新于 分类于

二维前缀和

简介

二维前缀和是前缀和差分中的一类，属于基础算法。通常用于求子矩阵元素的和。

假设有一个 \(n\times m\) 的矩阵，二维前缀和预处理复杂度为 \(O\left(nm\right)\) ，查询复杂度为 \(O\left(1\right)\) ，如果查询 \(q\) 次，那么暴力查询的复杂度为 \(O\left(nmq\right)\) ，而用二维前缀和则只需要 \(O\left(q\right)\) ，可见是不小的优化。

实现过程

预处理

实现这个算法需要先预处理一个二维数组 \(S\)，存放这个矩阵从 \(0,0\) 到 \(i,j\) 的子矩阵元素的和 \(\left(1\leq i\leq n,1\leq j \leq m\right)\) 。

这样子不好理解，我举一个例子：

在 \(3\times 3\) 的矩阵中，\(S_{2,2}\) 就指的是下图红色块的和：

那么，如何预处理矩阵呢？

参照上图矩阵，求 \(S_{2,2}\) ，就需要用 \(2\) 和 \(4\) \(\left( S_{2,1}\right)\) 加上 \(2\) 和 \(3\) \(\left(S_{1,2}\right)\) ，这样 \(2\) \(\left(S_{1,1}\right)\) 被加了两次，需要减去。这样就可以根据已知推出整个 \(S\) 矩阵了。

递推式： \[ S_{i,j}=S_{i-1,j}+ S_{i,j-1}-S_{i-1,j-1}+a_{i,j} \]

计算

给出的样例可不一定是左下角是 \(1,1\) 的矩阵。 比如求下图绿色部分的和，就要用 \(S_{3,3}\) 减去粉色部分的和。

现在的问题就是粉色部分怎么求。

把粉色部分分成两部分，一个是 \(S_{3,1}\) ，另一个是 \(S_{1,3}\) 。把它们加起来，就多了一个 \(S_{1,1}\) 在把它减去就可以了。

假设子矩阵左上角是 \(\left(x1,y1\right)\) ，右上角是 \(\left(x2,y2\right)\) ，那么矩阵的和为： \[ S_{x2,y2}-S_{\left(x1-1\right),y2}-S_{x2,\left(y1-1\right)}+S_{\left(x1-1\right),\left(y1-1\right)} \]

例题及讲解

直链

【入门】子矩阵求和

思路

模板题，就是求矩阵元素和，直接套公式，计算出来即可。

千万不要用暴力，复杂度会达到 \(O\left(2\times 10^{11}\right)\) ,小心TLE

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
#define debug cerr<<"The code runs successfully.\n";
#define endl '\n'
#define TRACE 1
#define tcout TRACE && cout
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
const int P = 998244353; 
const int Base = 3221225477;
const int INF = 0x3f3f3f3f3f3f3f3f; 
const int N = 1e3 + 10, M = 2e6 + 10;
int a[N][N],s[N][N];//全局全部赋值为0，访问S[0][0]不会爆掉
signed main()
{
	fst;
	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数组
			s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
		}
	}
	for(int i=0;i<q;i++)
	{
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
        //套用公式
		int ans=(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);
		cout<<ans<<endl;
	}
	return 0;
}