当前位置:首页 > 趣味小程序 > 正文内容

【算法】前缀和与差分(1)一维数组前缀和

亿万年的星光3年前 (2022-07-16)趣味小程序22452

一、定义

前缀和:是指某序列的前n项和。可以理解成数学上上的数列的前n项和。

差分:是前缀和的逆运算。


二、前缀和的分类

可以分成一维数组的前缀和和二维 数组的前缀和

  • 一维数组前缀和

    定义式:

        

 递推式:

    

  • 二维数组前缀和


定义式:

递推式:

    

三、解决什么问题

前缀和、差分是为了解决某一类问题。比如下面这道题目:

【题目描述】

输入一个长度为n的整数序列。接下来再输入M次询问,每个询问输入一对L, R。对于每次询问,输出原序列中从第L个数到第R个数的和。

【输入描述】

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

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

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

【输出描述】

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

【样例输入】

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

【样例输出】

3
6
10

【数据范围】

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

看到这个题目可能很多人会想到暴力求解方法,比如下面这样:

#include<iostream>
using namespace std;
int main(){
    int n,m,sum=0;
    int a[100]; 
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    //暴力求解
    while(m--){
        int L,R;
        int sum=0;
        cin>>L>>R;
        for(int i=L;i<=R;i++){
            sum+=a[i];
        }
        cout<<"sum="<<sum<<endl;  
    }
  
    return 0;
}


按照上面这样做的时间复杂度为O(n*m),如果nm的数据量稍微大一点就很可能超时,如果我们使用前缀和的方法来做的话就能够将时间复杂度降到O(n+m),提高了运算效率,避免超时问题。

 核心代码:

for (int i = 1; i <= n; i ++ ){
	cin >> a[i];
	s[i] = s[i - 1] + a[i];
}

特别是s[i]=s[i-1]+a[i]这行代码,这行代码拆解如下:

s[1]=s[0]+a[1]; //s[0]为0
s[2]=s[1]+a[2]=a[1]+a[2];
s[3]=s[2]+a[3]=a[1]+a[2]+a[3];
s[4]=s[3]+a[4]=a[1]+a[2]+a[3]+a[4];
......

按照上面这样,我们就能得到前缀和了。

我们这么做的优势在于:以O(1)的时间复杂度得到某块区间的总和。

那么,我们求区间和的过程就相对简单了。

因为L<=R, 所以我们可以参考下面的过程:

s[L]=a[1]+a[2]+a[3]+....+a[L]

s[R]=a[1]+a[2]+a[3]+...+a[L]+a[L+1]+a[L+2]+....+a[R]

我们要求的是a[L]+a[L+1]+...+a[R]。也就是s[R]-s[L-1];





然后我们的代码就可以参考下面这样写:

#include<iostream>
using namespace std;
int main(){
    int n,m;
    int a[100]={0};
	int s[100]={0}; 
    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;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:
返回列表

上一篇:EasyX小游戏—双人反弹球

没有最新的文章了...

相关文章

C++小游戏—贪吃蛇(1)

0.前言c++小游戏来到了第二个,第二个小游戏是贪吃蛇。首先来分析一下需求。我们需要一个函数专门来绘制地图的。在地图上随机生成“食物”。按键函数,用来监听键盘事件。蛇的状态函数。移动函数等。1.参考代...

C++小游戏—猜数游戏

0.游戏内容玩家猜电脑产生的数字,一个两次机会,才对了给提示,猜错减去一次机会。1.参考代码#include<iostream>#include<cstdlib>#includ...

【C++图形化编程】飞机大战2——运动与碰撞检测

上一篇中,简单实现了飞机大战的基本框架,这篇文章继续完善,使其可以进行游戏。#include <graphics.h> #include <conio.h>...

C++如何在控制台不同区域显示不同颜色

C++如何在控制台不同区域显示不同颜色

0.前言在前面的文章中,我们介绍过让控制台”五彩斑斓“。但是有一个问题,就是使用system(“color A9”)这种方式,这种方式是一种全局的配置,会把原来的颜色给换掉,很难实现不同区域不同颜色的...

【C++图形化编程】flappy bird(2)—游戏逻辑与完善

【C++图形化编程】flappy bird(2)—游戏逻辑与完善

0.前言    上一篇中,我们简单完成了flappy的图像导入和基本架构。这一篇文章中,我们继续完善。1.游戏逻辑这个游戏的简单逻辑就是:(1)初始状态(游戏一...

C++实现弹窗效果

C++实现弹窗效果

1.格式C++实现弹窗效果需要用到messagebox,这个我在C#中用过,C++也有类似用法。messagebox函数,需要引入<windows.h>头文件2.简单用法#include&...