倍增自学笔记
2025-07-23 22:44:51
发布于:上海
倍增
倍增思想似乎是人们数东西的时候下意识做出的举动的抽象映射.
比如说,你去上学的路上有一堆小石子,有10000颗.
那么你路程可能是这样的:1,2,3,4,(一颗一颗跳),6,8,10,12,14(两颗两颗跳)......
那么假设你的运动能力比较好,你可以这样条:1,2,4,8,16,32,64.....(有点扯,但就这样吧).
在网上找了一个合适的例子:(选在朝夕的文章,但把胡萝卜改成了数)
你有一堆无限且不同的数,现在需要你选出一些数,来凑齐[1,n]之间所有的数.
普通的方法:找出1,2,3,.....n.
高级的方法:找出1,2,4,8,16,32....>=n的
具体来说,只要你拥有1,2,4,8...,你就至少能表示出[1,]的数.
比如说:
我拥有1,2,4,8,16,32.
我可以表示出:
3:2+1/4-1
5:4+1/8-2-1
6:2+4
7:8-1
9:8+1
但是为什么?
为什么拥有就可以表示出[1,]的数?
可转换成: ->
-> 4
-> 2
-> 1
从开始:,我们就拥有了1,2,3,4.
然后就是,而8-4=4,想要凑出5-7,可以直接使用已经拥有的1-3,分别加4.
至此,初见端倪.
先要凑出到次方的数,需要所有至次方的数.而拥有了所有次方的数,就可以凑出到次方的数.
那么从看,我们已经有1至1的数().那么后续就像多米诺骨牌一样了.
那么也就是说,想凑数[1,n]的所有数,只需要的数.
那么再把这个(好像是)数学理论的东西搬到C++上,就意味着
在一些情况下,只需要的时间复杂度,就可以解决时间复杂度的问题.
即线性->对数.
而且可以从上述的推论中发现,倍增其实跟二进制有点关系.
ST表
*上方的描述都是在网上搜查得出的结论,下方的描述将会参考深入浅出程序设计竞赛(进阶篇)
ST表是运用倍增思想求取区间最值的算法.
题目:平衡的队列
想求一个序列A中,到最大值与最小值的差.(有q组问题,序列有n个数.
因为不可能直接求最大值与最小值的差,就将问题分解称分别求最大值和最小值.
最直接的做法是暴力枚举,但是时间复杂度为,不太可行.
效率低下的原因是询问的区间可能有大幅重叠.这些大幅重叠会产生大幅重复.
如果可以通过预处理得道一些小区间的最大值和最小值,再通过这些区间拼凑每一个区间,就可以提高效率.
那么就是这些"小区间"的选择了.
提到预处理,或许可以想到前缀和与差分:预处理前缀和数组可以随意拼出任意区间的和.
但是区间最值可能不行.为什么?
前缀和:
A:1,2,4,5,3.
推出:1,3,7,12,15.
区间最值:
A:1,2,4,5,3
推出:?
然后就发现,区间最值的预处理方式还是一个未知,不过至少会排除前缀和的预处理方式.
那为什么区间最值的预处理不能效仿前缀和的预处理方式?
可以发现:前缀和的预处理方式使用大区间推出小区间.
但是区间最值的处理却是小区间拼出大区间.
前缀和的预处理方式是从大区间中铲掉一块,使其变成小区间.
但是区间最值是不能从大区间中删去区间的.
比如上面的一组数据,[1,7,3,4,2,5]是数组A.
[1,7,7,7,7,7]是区间[1,i]的最大值.
如果说这是前缀和数组的话,它可以凭借[1,i]区间的和与[1,j]的和求出[i,j]的和.
但是区间最值不行.所以它只用小区间拼出大区间.
如何选择预处理的小区间成为关键.选择的区间既要能拼出任意区间,又要少.预处理和查询都要高效.
那么分为两个要求点:1.能品出任意区间 2.量少效率高.
首先考虑如何拼出任意区间:
对于一个下标为[1-i]的区间,想要用小区间最值拼出这个大区间的最值,你至少需要两个小区间:[1 - (i-x)] 和 [(i-x+1) - i].
然后想到(也可以想不到,直接看就行)ST表算法使用了倍增的思想.
倍增是种什么思想?对数相互连接,形成线性的桥梁.
人话就是你需要个过程才能解出答案,而倍增可以只有个过程,却可以解出正确的答案(考试时并不提倡,因为可能会扣过程分).
这里空空如也
有帮助,赞一个