算法中的二阶差分

众所周知,在往区间的每一个数都加上一个相同的数k,进行n次后会得到一个新的数列,如果每次加都循环区间挨个数加上k,这样时间复杂度无疑是O(n^2),很高。这时可以采用一阶差分就可解决,这里默认会一阶差分,所以就不多说了嘿嘿。

那如果是加上不同的数呢,比如说往区间[l,r]的l点加上数a,往l+1点加上数a+d,……。加的数形成等差数列,这该怎么办呢?这时可以用二阶差分。因为你想,对加上对应等差数列的不同的数进行一阶差分,是不是点的值都变成公差了,公差是不是都是一样的,那这时候再进行一次差分,就可以做到只改变区间某点的数据,实现区间的加减值。

如下图:

相关推荐

  1. 二分搜索详解

    2024-04-09 21:34:03       17 阅读
  2. C++ transformtoupper使用

    2024-04-09 21:34:03       37 阅读
  3. 贪心关于重叠区间问题感悟

    2024-04-09 21:34:03       31 阅读
  4. 动态规划在实践

    2024-04-09 21:34:03       17 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-04-09 21:34:03       18 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-04-09 21:34:03       19 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-04-09 21:34:03       18 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-04-09 21:34:03       20 阅读

热门阅读

  1. python爬虫基础知识整理(2)

    2024-04-09 21:34:03       12 阅读
  2. SQL语言

    SQL语言

    2024-04-09 21:34:03      15 阅读
  3. 如何使用Docker容器化改善你的开发流程

    2024-04-09 21:34:03       14 阅读
  4. == 和 ===什么区别呀?

    2024-04-09 21:34:03       16 阅读
  5. Pandas追加写入文件的时候写入到了第一行

    2024-04-09 21:34:03       13 阅读
  6. 程序员如何利用副业实现财务自由

    2024-04-09 21:34:03       16 阅读