【算法】前后缀

本文主要是介绍【算法】前后缀，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

目录

1.一维前缀和

1.1 朴素方法（此时时间复杂度为O(n)）

1.2 改进方法：

2. 二维前缀和

2.1 方法

2.2 代码

2.3 例题

1.一维前缀和

原数列a：1 2 3 4 5 6 7 8 9 s[i]=a[1]+a[2]...+a[i]

前缀和数列s：1 3 6 10 15 21 28 36 45

对于求区间[L,R]的前缀和：

1.1 朴素方法（此时时间复杂度为O(n)）

int main()
{
    int sum=0;
    for(int i=l;i<=R;i++)
        sum+=a[i];
}

1.2 改进方法：

首先算好前缀和，然后利用result=s[R]-s[L-1]

#include<iostream>
using namespace std;
int n,m;//输入数列个数与查询的次数
const int N=1001;
int a[N],s[N];//定义原数列与前缀和数列
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];//求前缀和
    }
    while(m--)
    {
        int L,R;
        cin>>L>>R;
        cout<<s[R]-s[L-1]<<endl;//利用前缀和求出来区间内的和
    }
    return 0;
}

2. 二维前缀和

2.1 方法

• 定义二维矩阵a

1 2 3 4
5 6 7 8

• 定义其前缀和矩阵sum

我们用数组sum[i][j]表示左上角a[1][1]到左下角a[i][j]的和，其中sum[3][4]即绿色部分的和

sum[i][j]的预处理：

你要算出黄绿蓝，三个部分的和，你要知道，当你再算sum[i][j]的时候已，即

sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]

1 3 6 10
6 14 24 36

• 利用前缀和矩阵求a的任意子矩阵的和。我们开始来看一看一个任意的以（x1,y1）为左上角，（x2,y2）为右下角的子矩阵怎么求：

  

首先这个矩阵的和肯定包括在sum[x2][y2]中，但是多了一些东西，所以我们要把蓝的，黄的，绿的部分减去，首先看如何减去蓝的，用最粗暴的方法，直接减掉sum[x1-1,y2],好现在只要减掉一个绿色部分就行了，依然用简单粗暴的办法，减掉sum[x2][y1-1]，但是此时黄色被减去了两次，所以需要在加回去。因此子矩阵的和就等于sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]

2.2 代码

#include<iostream>
#include<cstring>
using namespace std;
int a[2000][2000],sum[2000][2000];
int main()
{
    int n,m,q;//所给的矩阵是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];//输入原矩阵
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++)//前缀和
        for(int j=1;j<=m;j++)
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
    for(int i=1;i<=q;i++)//接受查询 
    {
        int x1,x2,y1,y2;
        cin >>x1>>y1>>x2>>y2;
        cout <<(sum[x2][y2]+sum[x1-1][y1-1]-sum[x1-1][y2]-sum[x2][y1-1])<<endl;//O（1）查询 
    }
    return 0;
} 

2.3 例题

A-激光炸弹

一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。现在地图上有n(N<=10000)个目标，用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的正方形的边必须和x，y轴平行。若目标位于爆破正方形的边上，该目标将不会被摧毁。

输入格式

输入文件的第一行为正整数n和正整数R，接下来的n行每行有3个正整数，分别表示xi,yi,vi

输出格式

输出文件仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过32767）。

Sample Input

2 1
0 0 1
1 1 1

simple output

1

代码

#include<iostream>
using namespace std;
int s[5010][5010];//定义前缀和数组
int main()
{
    int N, R;//N为目标数，R为能炸掉的正方形的边长
    cin >> N >> R;
    R = min(R, 5001);//地图范围一定，爆炸范围不需要很大，只需要考虑地图范围内即可
    for (int i = 1; i <= N; i++)//目标的输入
    {
        int x, y, w;
        cin >> x >> y >> w;
        s[++x][++y] += w;
        //x和y都可以取0，为了后面循环的方便，让他们都变到从1开始的位置
    }
    for (int i = 1; i <= 5001; i++)//对地图每个位置都求二维前缀和
    {
        for (int j = 1; j <= 5001; j++)
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    }
    int ans = 0;
    //由于在R-1或者之前的位置会消耗一部分地图外的，是没有价值的，所以从R,R开始
    for (int i = R; i <= 5001; i++)
        for (int j = R; j <= 5001; j++)
            ans = max(ans, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]);
            //求原来最大的与当前遍历到的RxR的正方形的所有价值总和的最大值
    cout << ans;
    return 0;
}
​

B-子矩阵求和

给出一个m * n的矩阵a，矩阵元素a[i,j]小于1000，进行q次查询，每次查询给出子矩阵的4个边界（上下左右），求该子矩阵所有元素之和。

样例中第一个查询：1 3 1 2 表示从第1行到第3行，从第1列到第2列，对应的子矩阵是：

1 2
5 6
9 10

求和等于33

Input

第一行2个整数n, m，中间用空格分割，分别对应数组的行数n、列数m(1 <= m,n <= 100) 接下来n行，每行m个整数表示矩阵的内容a[i,j] 。(0 <= a[i,j] <= 1000) 接下来1行，一个数q，对应查询的数量。(1 <= q <= 1000) 接下来q行，每行4个整数，对应矩阵的上下左右边界u,d,l,r。(1 <= u <= d <= n, 1 <= l <= r <= m)

Sample Input

3 4
1 2 3 4
5 6 7 8
9 10 11 12
3
1 3 1 2
1 2 1 3
1 3 1 3

Output

输出共q行，对应q个询问的求和结果。

Sample Output

33
24
54

代码

#include<iostream>
using namespace std;
int main()
{
    int a[100][100];
    int n,m;
    int q;
    int u, d, l, r, value, ans;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> value;
            a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + value;
        }
    }
    cin >> q;
    while (q--) {
        cin >> u >> d >> l >> r;
        ans = a[d][r] - a[d][l - 1] - a[u - 1][r] + a[u - 1][l - 1];
        cout << ans << endl;
    }
    return 0;
}

这篇关于【算法】前后缀的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！