(一) 题目传送门
什么是前缀和?
原数组: a[1],a[2],a[3],a[4],a[5],…,a[n]
前缀和 Si为数组的前i项和
前缀和: S[i]=∑ik=1ak
注意:为避免边界情况,前缀的下标统一从1开始
前缀和的作用?
快速求出一段连续区间的和
例如求区间[l,r]的和,就应该是Sr−Sl−1
#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int main()
{
int n , q;
cin >> n >> q;
for(int i = 1 ; i <= n ; i++ )
{
int x;
cin >> x;
a[i] = a[i - 1] + x;
}
while(q--)
{
int l , r;
cin >> l >> r;
cout << a[r] - a[l - 1] << endl;
}
return 0;
}
(二) 题目传送门
将一维前缀和推广向二维,那么s[i][j]就表示以一个矩阵的和,且(1,1)为矩形左上角,(i,j)为矩阵右下角
如何计算s[i][j]?
如下图所示,通过两个矩阵的和相加减掉重复矩阵再加上(i,j)原来的值,就可以计算出s[i][j];
不难发现s[i−1][j]、s[i][j−1]、s[i−1][j−1]已经在计算s[i][j]之前已经被计算过了。
如何通过矩阵前缀和来求得一个矩阵的和?
如下图所示,因为起点都是(1,1),所以可以用一个大矩阵,减掉两个小矩阵,再加回一个重复减掉的小矩阵即可
#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N] , n , m , q;
int main()
{
cin >> n >> m >> q;
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= m ; j ++)
{
cin >> a[i][j];
a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
}
while(q--)
{
int x1 , y1 , x2 ,y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << a[x2][y2] - a[x2][y1 - 1] - a[x1 - 1][y2] + a[x1 - 1][y1 - 1] << endl;
}
}
(三) 题目传送门
什么是差分?
首先给定一个原数组a:a[1],a[2],a[3],,,,,,a[n];
然后我们构造一个数组b:b[1],b[2],b[3],,,,,,b[i];
使得 a[i]=b[1]+b[2]+b[3]+,,,,,,+b[i]
也就是说,a数组是b数组的前缀和数组,反过来我们把b数组叫做a数组的差分数组。换句话说,每一个a[i]都是b数组中从头开始的一段区间和。
如何构造差分数组?
最直接的方法如下:
a[0 ]= 0;
b[1] = a[1] - a[0];
b[2] = a[2] - a[1];
b[3] =a [3] - a[2];
........
b[n] = a[n] - a[n-1];
我们只要有b数组,通过前缀和运算,就可以在O(n) 的时间内得到a数组。
那么如何用差分解决这道区间修改的问题呢?
我们可以进行如下操作:
1、先将b[l]加上c,此时再计算a数组,应该是如下:a[1]、a[2]、a[3]、…、a[l]+c、a[l+1]+c、…a[r+1]、a[r+1]、…a[n]+c
2、显然此时还是不够的,因为从r+1开始,之后的一段区间是没必要+c的,因此我们只需要将a[r+1]减c即可
#include <iostream>
using namespace std;
const int N = 100010;
int n , m , a[N] , b[N];
int main()
{
cin >> n >> m;
for(int i = 1 ; i <= n ; i++)
{
cin >> a[i];
b[i] = a[i] - a[i - 1];
}
while(m--)
{
int l , r , c;
cin >> l >> r >> c;
b[l] += c , b[r + 1] -= c;
}
//b数组的前缀和数组就是原数组
for(int i = 1 ; i <= n ; i++)
{
b[i] += b[i - 1];
cout << b[i] << ' ';
}
}
(四) 题目传送门
有了一维差分的基础,我们知道差分数组的前缀和数组就是原数组,因此我们只需要将差分操作记录下来既可以,然后通过差分矩阵还原出原矩阵即可。
#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N];
int n , m, q;
//以(i,j)右下方的点,在计算前缀和时都会累加上a[i][j],
//因此如果想给以(x1,y1)为左上角,以(x2,y2)为右下角的矩阵加上c这个差分值,
//需要进行如下操作,这样可既不多加也不少加
//类似于矩阵前缀和,需要把握每个点影响的都是它右下方的点这个思想
void insert(int x1 , int y1 , int x2 , int y2 , int c)
{
a[x1][y1] += c;
a[x1][y2 + 1] -= c;
a[x2 + 1][y1] -= c;
a[x2 + 1][y2 + 1] += c;
}
int main()
{
cin >>n >> m >> q;
for(int i = 1; i <= n ; i++)
for(int j =1 ; j <= m ; j++)
{
int x;
cin >> x;
insert(i , j , i , j , x);//原数组的(i,j)上是x,相当于在(i,j)到(i,j)这个矩阵范围里加上x
}
while(q--)
{
int x1 , x2 , y1 , y2 , c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
insert(x1 , y1 , x2 , y2 , c);
}
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= m ; j++)
{
a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
cout << a[i][j] << ' ';
}
cout << endl;
}
return 0;
}
### %%%%