Java教程

【算法】前后缀

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

目录

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
  • 定义其前缀和矩阵sumimg

我们用数组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;
}

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