首页 > 其他 > 详细

差分 & 前缀和

时间:2019-07-31 22:45:14      阅读:111      评论:0      收藏:0      [点我收藏+]

我们从问题入手。

 

入门问题:有已赋值的 n 个数,现在有 m 个指令

操作 1: 每一次要求将第 k 个数加上 a,最后求所有数的值;

操作 2: 查询第 k 个数字的值。

$1 ≤ k ≤ n ≤ 10^5$

这一题其实用一个数组就可以维护。

 


 

 

问题一:有已赋值的 n 个数,现在有 m 个指令,每一个指令要求查询第 x 个数到第 y 个数的和。

$1 ≤ x ≤ y ≤ n,m ≤ 10^5$

如果暴力求和是会 TLE 的。

那应该如何解决这个问题呢?

这就要引出前缀和了。

可以看出,$\sum_{i=x}^ya_i = \sum_{j=1}^ya_j - \sum_{k=1}^{x-1}a_k$

所以我们只需要求第一个数到各个数的和即可。

求这些数很容易,O(n) 复杂度递推,接下来就可以 O(1) 查询了。

 


 

 

问题二:有已赋值的 n 个数,现在有 m 个指令,每一次要求将第 x 个数到第 y 个数加上 a,最后求所有数的值。

$1 ≤ x ≤ y ≤ n,m ≤ 10^5$

其实这题分块、线段树、树状数组以及其它的很多算法都可以过这题。

但是请看下一个问题:

 

问题三:有已赋值的 n 个数,现在有 m 个指令,每一次要求将第 x 个数到第 y 个数加上 a,最后求所有数的值。

$1 ≤ x ≤ y ≤ n,m ≤ 5*10^6$

我们发现:这个 5e6 的范围太大了,O(n log n) 以及更慢的复杂度是过不了的。

所以,下一个内容是:

 


 

差分

① 什么是差分?

差分,就是一个通过常数复杂度的标记实现求和及询问的一种技巧。

一般适合静态维护(前面先加,最后求值)。

 

② 差分怎么用?

我们马上举一个例子:

有一个数列:

    1  9  2  8  3  7  4  6  5
tag:  0 0 0 0 0 0 0 0 0  // 现在还没有打上标记

现在,我们将第 3 个数到第 5 个数加上 2.

那我们就发现,可以把第 3 个数开始把后面所有的数加上 2,再从第 6 个数开始把后面所有数减去 2 呢,就相当于把第 3 个数到第 5 个数加上 2 了。

然后这么标记:

a[i]:  1  9  2  8  3  7  4  6  5
tag :  0  0  2  0  0  -2 0  0  0  // 打上标记*1

然后,我们再将第 4 个数到第 8 个数减去 1.

按照上面的想法,我们可以从第 4 个数开始把后面所有的数减去 1,在从第 9 个数开始把后面所有的数加上 1.

a[i]:  1  9  2  8  3  7  4  6  5
tag :  0  0  2 -1  0 -2  0  0  1  // 打上标记*2

假设指令执行结束,那么我们这样求和:

用一个 sum 数组记录,$sum_i$ 代表前 i 个数所带的 tag 的和。

a[i]    :  1  9  2  8  3  7  4  6  5
tag     :  0  0  2 -1  0 -2  0  0  1  
sum[i] : 0 0 2 1 1 -1 -1 -1 0

最后,我们把 $a_i$ 加上对应的 $sum_i$ 相加,就是答案了。(这里有用到前缀和的思想)

时间复杂度 O(n).

 

总结

与其说这是一个算法,不如说这是一个思想。

我们会碰到很多这样的题目,看似需要比较复杂的数据结构,其实很简单。

这需要我们灵活运用所学的知识。

差分 & 前缀和

原文:https://www.cnblogs.com/zengpeichen/p/11279207.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!