算法学习专栏——一、二维前缀和

前言

​ 接下来两天介绍的算法还算比较轻松，打算今日讲解一维前缀和和二维前缀和。

​ 但是这种类型的题目出现在比赛中就绝对不是这种形式了，一般就是以一种完全不一样的模式出现的。下面的激光炸弹是几年前蓝桥杯的一道C++组真题。

一、前缀和（一维）（简单-）

输入一个长度为 n 的整数序列。

接下来再输入 m 个询问，每个询问输入一对 l,r,。

对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。

输入格式

第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示整数数列。

接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。

输出格式

共 m 行，每行输出一个询问的结果。

数据范围

1≤l≤r≤n1
1≤n,m≤100000
−1000≤数列中元素的值≤1000

输入样例：

1
2
3
4
5
5 3
2 1 3 6 4
1 2
1 3
2 4

输出样例：

1
2
3
3
6
10

思路

代码

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
#include < iostream>
#include < algorithm>
using namespace std;
const int N = 1010;
int a[N][N], s[N][N];
int n, m, q;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];    
        }
    }  
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++) {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }
    while (q--) {
        int x1, y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << '\n';
    }
    return 0;
}

二、前缀和（二维）（简单+）

输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y21,1,2,2，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式

第一行包含三个整数 n，m，q，，。

接下来 n 行，每行包含 m 个整数，表示整数矩阵。

接下来 q 行，每行包含四个整数 x1,y1,x2,y21,1,2,2，表示一组询问。

输出格式

共 q 行，每行输出一个询问的结果。

数据范围

1≤n,m≤1000
1≤q≤200000
1≤x1≤x2≤n
1≤y1≤y2≤m
−1000≤矩阵内元素的值≤1000

输入样例：

1
2
3
4
5
6
7
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

输出样例：

1
2
3
17
27
21

思路

​ 直播（录屏）

代码

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
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;
int a[N][N], s[N][N];
int n, m, q;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];    
        }
    }
    
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++) {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }
    
    while (q--) {
        int x1, y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << '\n';
    }
    return 0;
}

三、激光炸弹（蓝桥杯，中等-）

地图上有 N 个目标，用整数 Xi,Yi, 表示目标在地图上的位置，每个目标都有一个价值 Wi。

注意：不同目标可能在同一位置。

现在有一种新型的激光炸弹，可以摧毁一个包含 R×R× 个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 x，y， 轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式

第一行输入正整数 N 和 R，分别代表地图上的目标数目和正方形包含的横纵位置数量，数据用空格隔开。

接下来 N 行，每行输入一组数据，每组数据包括三个整数 Xi,Yi,Wi,,，分别代表目标的 x 坐标，y 坐标和价值，数据用空格隔开。

输出格式

输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围

0≤R≤10^9^
0<N≤100000
0≤Xi,Yi≤50000
0≤Wi≤10000

输入样例：

1
2
3
2 1
0 0 1
1 1 1

输出样例：

1
1

思路

代码

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
#include < iostream>
#include < cstring>
#include < algorithm>
using namespace std;
const int N = 5010;
int n, r, a, b, res;
int arr[N][N];
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> r;
    r = min(5001,r);
    a = max(a, r);
    b = max(b, r);
    while(n--)
    {
        int x, y, w;
        cin >> x >> y >> w;
        ++x;
        ++y;
        a = max(x,a);
        b = max(y,b);
        arr[x][y] += w;
    }
    for (int i = 1; i <= a; i ++ )
    {
        for (int j = 1; j <= b; j++)
            arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
    }
    for (int i = r; i <= a; i ++ )
    {
        for (int j = r; j <= b; j++)
            res = max(res, arr[i][j] - arr[i - r][j] -arr[i][j - r] + arr[i - r][j - r]);          
    }    
    cout << res;    
    return 0;
}