您现在的位置是:首页 > 正文

差分算法(用python语言实现)

2024-01-30 21:35:14阅读 0

一.差分

1.介绍

一般地,差分主要用于多次将某个序列的某一段加上或减去某一特定值。相对于一个元素一个元素地加,大大减少了时间复杂度

2.定义

差分可以见简单看成序列中每一个元素与其前一个元素的差

3.差分与前缀和

   一般地,我们认为原序列就是差分序列的前缀和,所以把差分看做前缀和的逆运算

二.一维差分

1.定义

一维差分是指给定一个长度为n的序列a,要求支持操作pro(l,r,c)表示对a[l]~a[r]区间上的每一个值都加上或减去常数c,并求修改后的序列a。(注:我们是借助差分这个工具来对原序列的某一段进行改变,所以最终的结果还是要反映到原序列上的)

2.作用

可以将对a数组任意区间的同一操作优化到O(1)。

举个栗子:

如果我想对如下序列的子序列2~6的这一段数据上加上3,为4~8这一段的数据都加上2

l=[0,2,3,5,6,7,7,8,9,10,1,2]


l=[0,2,3,5,6,7,7,8,9,10,1,2]
for i in range(2,7):
  l[i]+=3
for i in range(4,9):
  l[i]+=2
for i in range(12):
  print(l[i])

#在这里我们只要求将给两段上加上了特定的值
#但是如果我们要求给n个子序列上加上特定的值  并且每个子序列的中的元素都不小于m
#那么我们就要遍历长度不小于的m序列 并且要遍历n次  时间复杂度为O(m*n) 就会特别耗时

但是如果用差分的话就会简便很多:


def insert(b,l,r,c):
  b[l]+=c
  b[r+1]-=c

if __name__ == "__main__":
  l=[0,2,3,5,6,7,7,8,9,10,1,2] 
  l,r,c=map(int,input().split())
  insert(b,2,6,3)#如果我子序列中有m个元素 那么这里直接从O(m)降到了O(1)
  insert(b,4,8,2)
  for i in range(1,12):
    b[i]+=b[i-1]
  for i in range(1,12):
    a[i]+=b[i]
    print(a[i],end=' ')

3.两种模板

 1.先构建原序列差分数组,然后直接在差分数组上进行操作,最后直接求出此差分数组的前缀和,便是最后的经过几波操作后的结果序列。

 2.开始将差分数组都赋值为0,然后对差分数组进行操作,最后将差分数组的前缀和与原数组相加便是最后的结果。

4.实战演练

题目链接:https://www.acwing.com/problem/content/799/

用第一个模板写


def insert(b,l,r,c):
  b[l]+=c
  b[r+1]-=c

if __name__ == "__main__":
  n,m=map(int,input().split())
  a=[0]*(n+10)#元序列
  b=[0]*(n+10)#差分序列
  nums=list(map(int,input().split()))
  for index,val in enumerate(nums):#这里的enumerate函数可以直接罗列出此列表中的下标和元素
    a[index+1]=val

  for i in range(m):
    l,r,c=map(int,input().split())
    insert(b,l,r,c)
  for i in range(1,n+1):
    b[i]+=b[i-1]#求差分序列的前缀和
  for i in range(1,n+1):
    a[i]+=b[i]#再将两个序列相加  将差分序列的作用反映到原序列上
    print(a[i],end=' ')

用第二个模板写

def insert(b, l, r, c):
    b[l] += c
    b[r+1] -= c

if __name__ == "__main__":
    n, m = map(int, input().split())
    a = [0] * (n + 10)  
    b = [0] * (n + 10)  #
    nums = list(map(int, input().split()))
    for index, val in enumerate(nums):
        a[index+1] = val
    for i in range(1, n+1):  
        insert(b, i, i, a[i])#构造差分序列
    while m > 0:
        m -= 1
        l, r, c = map(int, input().split())
        insert(b, l, r, c)
    for i in range(1, n+1):
        b[i] += b[i-1]
        print(b[i],end=" ")#直接输出差分序列的前缀和就好

网站文章

  • 《美图数据统计分析平台架构演进》阅读有感

    《美图数据统计分析平台架构演进》阅读有感

    《美图数据统计分析平台架构演进》阅读有感数据统计是一个比较尴尬的事情,第一个它可能不是一个非常有技术含量的事情,对于技术人员的成长来说不是非常好。第二它可能是一个比较重复工作的事,需要解决一些简单的需求的重复工作。统计业务与技术碰撞这基本上是我自己亲身的经历,刚开始一个人做这一块的业务,会碰到一些有意思的点,可能分三个阶段,第一个阶段是在项目的初期,我们是怎么样去应对一些产品的初期需求...

    2024-01-30 21:34:45
  • unity 3.6在import package时只有custom package

    unity 3.6在import package时只有custom package

    【问题描述】下载的unity 3.6在import package时只有custom package没有其他包文件【解决方案】在asset store里搜索Standard Assets选择导入即可导入完成后在左下角的project assets中多了一个Standard Assets文件夹打开即可使用...

    2024-01-30 21:34:37
  • LLCC68寄存器模式开发-几个关键操作说明

    LLCC68寄存器模式开发-几个关键操作说明

    llcc68 lora模式寄存器说明

    2024-01-30 21:34:29
  • RxJava 两种生产和消费模式,(冷)cold和(热)hot

    RxJava目前有两种发布和订阅模式。

    2024-01-30 21:34:23
  • (pytorch进阶之路)四种Position Embedding的原理及实现

    (pytorch进阶之路)四种Position Embedding的原理及实现

    定义子函数,获得每个window中两两patch之间二维的位置偏差,使用torch.meshgrid函数,根据x轴和y轴范围得到网格每个点的x坐标和y坐标,将其堆叠,获取任何两个点之间的横轴与纵轴坐标...

    2024-01-30 21:33:56
  • otter学习 | canal和otter的关系? 热门推荐

    otter学习 | canal和otter的关系? 热门推荐

    在回答这问题之前,首先来看一张canal&otter和mysql复制的类比图: mysql的自带复制技术可分成三步: master将改变记录到二进制日志(binary log)中(这些记录叫做二进制日志事件,binary log events,可以通过show binlog events进行查看); slave将master的binary log events拷贝到它的中继日志(...

    2024-01-30 21:33:49
  • 设计模式(19)命令模式

    设计模式(19)命令模式

    1、定义:命令模式(Command Pattern)是一种行为设计模式,它将请求封装为一个对象,从而使你可以使用不同的请求对客户端进行参数化。(2)具体命令类(Concrete Command):实现...

    2024-01-30 21:33:42
  • 自定义线程池

    自定义线程池

    一:参数分析 我们要想自定义线程池,必须先了解线程池的工作流程,才能自己定义线程池。下图是ThreadPoolExecutor的构造方法。 我们可以通过下面的场景理解ThreadPoolExecuto...

    2024-01-30 21:33:13
  • MobaXterm登录密码重置问题

    MobaXterm登录密码重置问题

    登录MobaXterm提示输入密码,密码输入多次后无果,密码忘记如法使用MobaXterm软件,经过查询后可采用密码重置的方式处理。使用浏览器打开如下网址:https://mobaxterm.moba...

    2024-01-30 21:33:04
  • 括号匹配数据结构

    学习分享本周学习的是数据结构的括号匹配,所谓括号匹配指的是在命令端输入一行只含有括号的代码,然后运行代码,判断每一个左括号是否有一个右括号与之对应,从而判断输入的数据是否违法代码如下:#define ...

    2024-01-30 21:32:57