第四章:前缀和、差分(数列)

这篇具有很好参考价值的文章主要介绍了第四章:前缀和、差分(数列)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、前缀和

1、 什么是前缀和

在解释什么是前缀和之前,我们先回顾一下高中学过的数列:第四章:前缀和、差分(数列)
我们这里所说的前缀和其实就是我们在高中学的数列中的Sn(前n项和),只是我们这里需要将S1 , S2 , S3 , S4 …… Sn当作一个新的数组。

为了这个式子的高度统一性,我们的S0和a0都是不存储数据的,将其设置为0,这样当n等于1的时候,也满足上面的式子。

2、 前缀和的作用

我们看下面这段数学推导:
第四章:前缀和、差分(数列)

如果我们想特定几项an的和,那么我们就需要取遍历数组an,然后才能求出最终的和,我们发现这种情况的时间复杂度是O(N)
但是我们使用前缀和Sn去计算的话,我们发现只需要一个简单是式子,其时间复杂度是O(1)。因此,我们便能够发掘出前缀和的作用:更快地求解数列的和
而这除了是利用了数学中的数列知识,更是一种用空间换时间的重要思想。

3、 前缀和的例题和模板

(1)一维数组的前缀和

其实前缀和就是一个公式,因此其模板是很简单的。
第四章:前缀和、差分(数列)

C++版
#include<iostream>
using namespace std;
const int N=1e6+10;
int arr[N];
int S[N];
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
    for(int i=1;i<=n;i++)S[i]=S[i-1]+arr[i];
    
    while(m--)
    {
        int l,r;
        scanf("%d %d",&l,&r);
        printf("%d\n",S[r]-S[l-1]);
    }
    return 0;    
}
C版
#include<stdio.h>
const int N=1e6+10;

int main()
{
	int arr[N];
	int S[N];
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
    for(int i=1;i<=n;i++)S[i]=S[i-1]+arr[i];
    
    while(m--)
    {
        int l,r;
        scanf("%d %d",&l,&r);
        printf("%d\n",S[r]-S[l-1]);
    }
    return 0;    
}

(2)二维数组的前缀和

a.思路:

在了解思路之前,我们应该先明白,什么是二维数组的前缀和,即二维数组的前n项和所指的是哪几项的和?
第四章:前缀和、差分(数列)
如图中所示,二维数组的前缀和就是图中方形所覆盖的an的和,包括边界!!!!

那么我们如何利用递推公式写出前缀和呢?
如下图所示:
第四章:前缀和、差分(数列)

那么在理解了二维数组的前缀和的概念后,我们看下面这个问题:
我们如何计算这个紫色方形范围内的an的面积呢?
第四章:前缀和、差分(数列)

图中所示的求法类似于我们高中所学的概率内容中的容斥原理
即我们先减去两部分,然后再加上重复减去的部分。但是我们要时刻注意边界问题,图中的式子之所以减一,就是因为紫色方形的边界也要算到前缀和中。

b.题目和模板:

题目:
第四章:前缀和、差分(数列)

C++版
#include<iostream>
using namespace std;
const int N=1010;
int a[N][N];
int S[N][N];
int main()
{
    int n,m,q;
    scanf("%d %d %d",&n,&m,&q);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&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;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        printf("%d\n",S[x2][y2]-S[x2][y1-1]-S[x1-1][y2]+S[x1-1][y1-1]);
    }
    return 0;
}
C版
#include<stdio.h>
const int N=1010;

int main()
{
	int a[N][N];
	int S[N][N];
    int n,m,q;
    scanf("%d %d %d",&n,&m,&q);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&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;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        printf("%d\n",S[x2][y2]-S[x2][y1-1]-S[x1-1][y2]+S[x1-1][y1-1]);
    }
    return 0;
}

二、差分

1、什么是差分?

我们知道前缀和是一个数组中的前N项和,其实差分就是原数组an。

因此我们就能够发现,一个数列当中,an是差分,an的前n项和sn是前缀和。

2、差分有什么作用?

我们通过前缀和可以在时间复杂度为O(1)的情况下,计算出几项的和。那么差分则可以在时间复杂度为O(1)的情况下,给数列中的某几项都加上常数C。假设我们不适用差分的话,我们需要遍历原数组然后逐一加上常数C,此时的时间复杂度就是O(N)

由此我们就能够总结出差分的作用:在时间复杂度是O(1)的前提下,将数组中的某几项加上特定的常数C。那么怎么加呢?我们看下面的内容。

3、一维差分:

(1)思路:

我们应该如何实现上面所说的差分的作用呢?我们看下面这张图片:
第四章:前缀和、差分(数列)
由上图可知:
我们只需要将bn中的第L项加上C,第r+1项减去C即可。这样我们在通过bn算an的时候,就能够在L到r的闭区间上的an都加上常数C。但此时的时间复杂度仅仅是O(1)

(2)题目和模板

第四章:前缀和、差分(数列)

C++版
#include<iostream>
using namespace std;
const int N=100001;
int a[N];
int b[N];
int main()
{
	//读取数据
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    //构造b数组:使得ai是bi的前缀和
    for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];
    
    while(m--)
    {
    	//读取插入的区间和数据
        int l,r,c;
        scanf("%d %d %d",&l,&r,&c);
        b[l]+=c;
        b[r+1]-=c;
    }
    //利用b数组打印a数组
    for(int i=1;i<=n;i++)printf("%d ",b[i]+=b[i-1]);
    return 0;
}
C版
#include<stdio.h>

const int N=100001;

int main()
{
    int a[N];
    int b[N];
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];
    
    while(m--)
    {
        int l,r,c;
        scanf("%d %d %d",&l,&r,&c);
        b[l]+=c;
        b[r+1]-=c;
    }
    
    for(int i=1;i<=n;i++)printf("%d ",b[i]+=b[i-1]);
    return 0;
}

(3)优化

这里我们在介绍一种不用特意构造b数组的方法。
我们假设an数列初始化全为0,那么此时我们输入a1的时候,就相当于在[1,1]上插入一个a1。同理,an就相当于在[n,n]上插入一个an。我们就能够采用这种方式来初始化bn数组,如果不理解的话,大家可以自己写几个例子。

C++版
#include<iostream>
using namespace std;
const int N=100010;
int a[N],b[N];

void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}

int main()
{
    int n,m;
    cin>>n>>m;
    
    for(int i=1;i<=n;i++)
    {   
        scanf("%d",a+i);
        insert(i,i,a[i]);
    }
    while(m--)
    {
        int l,r,c;
        scanf("%d %d %d",&l,&r,&c);
        insert(l,r,c);
    }
    for(int i=1;i<=n;i++)printf("%d ",b[i]+=b[i-1]);
    return 0;
}
C版
#include<stdio.h>
int a[100010],b[100010];
void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}

int main()
{
   
    int n,m;
    scanf("%d %d",&n,&m);
    
    for(int i=1;i<=n;i++)
    {   
        scanf("%d",a+i);
        insert(i,i,a[i]);
    }
    while(m--)
    {
        int l,r,c;
        scanf("%d %d %d",&l,&r,&c);
        insert(l,r,c);
    }
    for(int i=1;i<=n;i++)printf("%d ",b[i]+=b[i-1]);
    return 0;
}

4、二维差分:

(1)思路:

我们先上下面的图示:
第四章:前缀和、差分(数列)
先解决第一个问题,为什么b[i,j]+c后是右下角的数列元素加c呢?其实很好理解,因为an是bn的前n项和,因此只有右下角的an计算时,才会包括该点。因此,b[i,j]+c后影响的是右下角。
然后我们就可以根据上图中公式使得黄色区域的an都加上C。

(2)题目和模板

第四章:前缀和、差分(数列)文章来源地址https://www.toymoban.com/news/detail-403856.html

C++版
#include<iostream>
using namespace std;

const int N=1010;
int a[N][N];
int b[N][N];

void insert(int x1,int y1,int x2,int y2,int c)
{
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}

int main()
{   
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            insert(i,j,i,j,a[i][j]);
        }
    }
    while(q--)
    {
        int x1,y1,x2,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][j-1]+a[i-1][j]-a[i-1][j-1]+b[i][j];
            printf("%d ",a[i][j]);
        }
        cout<<endl;
    }
    return 0;
}
C版
#include<stdio.h>

int a[1010][1010];
int b[1010][1010];

void insert(int x1,int y1,int x2,int y2,int c)
{
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}

int main()
{   
    int n,m,q;
    scanf("%d %d %d",&n,&m,&q);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            insert(i,j,i,j,a[i][j]);
        }
    }
    while(q--)
    {
        int x1,y1,x2,y2,c;
        scanf("%d %d %d %d %d",&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][j-1]+a[i-1][j]-a[i-1][j-1]+b[i][j];
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

到了这里,关于第四章:前缀和、差分(数列)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第四章 Text

    在本章中,您将学习如何在页面上绘制文本。 绘图文本是 PDF 图形中最复杂的部分,但它也是帮助 PDF 击败竞争对手成为当今国际标准的原因。 当其他原始播放器将文本转换为光栅图像或矢量路径(以保持视觉完整性)时,PDF 的发明者知道用户需要可以搜索和复制的文本,而

    2024年02月06日
    浏览(46)
  • 四,Eureka 第四章

           2.3.4修改主启动类 标注为Eureka客户端           springcloud-eureka-sever-7001 springcloud-eureka-sever-7001   springcloud-eureka-sever003           5.25编写PaymentMapper接口   5.    

    2024年02月15日
    浏览(82)
  • 第四章 单例模式

    代码示例 优缺点:可能会造成内存的浪费,但也只能浪费内存 代码示例 代码示例 缺点:多线程不安全 缺点效率太低 在类加载时,静态内部类没有调用是不会进行类加载的,当被调用时才会被加载,而且只加载一次,加载时线程安全 优缺点

    2023年04月21日
    浏览(56)
  • 第四章-边界安全

    1)什么是防火墙 墙,始于防,忠于守。从古至今,墙予人以安全之意。 防御外网对内网的入侵 防火墙是一种 网络安全设备或系统 ,用于监控和控制网络流量,防止未经授权的访问和攻击。防火墙可以根据预定的规则和策略,过滤入站和出站数据包,保护网络的安全性和完

    2024年01月19日
    浏览(50)
  • 第四章网关

    Spring Cloud Gateway 是 Spring Cloud 的一个全新项目,该项目是基于 Spring 5.0,Spring Boot 2.0 和 Project Reactor 等响应式编程和事件流技术开发的网关,它旨在为微服务架构提供一种简单有效的统一的 API 路由管理方式。 Gateway网关是我们服务的守门神,所有微服务的统一入口。 网关的核

    2024年02月10日
    浏览(53)
  • 第四章 数组

    可以多看几遍视频 把上课的代码,自己加加注释,在自己写之前,可以画一个流程图 照着流程图把代码自己实现一遍 不要怀疑自己,不要遇到困难就觉得自己不行,遇到困难就解决困难,编程初学者都是这样一步一步走过来的。 在指针阶段会演示整型、浮点型、字符型传递

    2024年02月12日
    浏览(46)
  • 第四章 路由基础

    目录 4.1 路由器概述 4.1.1 路由器定义 4.1.2 路由器工作原理 4.1.3 路由表的生成方式 (1)直连路由 (2)静态路由 (3)动态路由 4.1.4 路由器的接口 (1)配置接口 (2)局域网接口 (3)广域网接口 4.1.5 路由器的硬件连接 (1)局域网线缆:双绞线 (2)广域网接口 (3)配置专

    2024年02月08日
    浏览(64)
  • 第四章 磁盘设备

    第四章 磁盘设备 一、 关于挂装的基本常识 •与 DOS/Windows 采用驱动器标识符(A:、B:、C:)使用磁 盘设备的方法不同。Linux 采用单根目录树管理全部文件系 统。磁盘设备必须挂载到系统目录树上才能使用。 (Linux 启动过程已完成对/、/ boot 和/swap 三个分区的挂装) •所谓挂

    2024年02月03日
    浏览(46)
  • 第四章 搜索功能

    指定返回的字段 在ES中,通过_source子句可以设定返回结果的字段。_source指向一个JSON数组,数组中的元素是希望返回的字段名称。 例如,通过source指定查询字段 结果计数 给前端传递搜索匹配结果的文档条数,即需要对搜索结果进行计数。ES提供了_count API功能,在该API中,用

    2023年04月08日
    浏览(41)
  • 第四章 RPC 调用

    通过以上案例我们发现,Http请求调用服务实例属实过于麻烦。其实对于请求同一个服务,很多步骤都是相同的,例如:服务名,地址,httpClient 创建步骤等。 RPC的出现,就是为了解决这一问题。 RPC: 即我们常说的远程过程调用,就是像调用本地方法一样调用远程方法,通信协

    2024年02月04日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包