倍增
倍增思想似乎是人们数东西的时候下意识做出的举动的抽象映射.
比如说,你去上学的路上有一堆小石子,有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的2i2^{i}2i
具体来说,只要你拥有1,2,4,8...2i2^i2i,你就至少能表示出[1,2i2^i2i]的数.
比如说:
我拥有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
但是为什么?
为什么拥有20,21,22,23,24,25...2n2^0,2^1,2^2,2^3,2^4,2^5...2^n20,21,22,23,24,25...2n就可以表示出[1,2n2^n2n]的数?
可转换成:2i,2i+1,2i+2,2i+3,2i+42^i,2^{i+1},2^{i+2},2^{i+3},2^{i+4}2i,2i+1,2i+2,2i+3,2i+4 -> [1,2i+3][1,2^{i+3}][1,2i+3]
2i+2−2i+1=2i+12^{i+2}-2^{i+1}=2^{i+1}2i+2−2i+1=2i+1
2i+1−2i=2i2^{i+1}-2^{i}=2^{i}2i+1−2i=2i
23−22=222^{3}-2^{2}=2^{2}23−22=22 -> 4
22−21=212^{2}-2^{1}=2^{1}22−21=21 -> 2
21−20=202^{1}-2^{0}=2^{0}21−20=20 -> 1
从222^222开始:21+20=32^1+2^0=321+20=3,我们就拥有了1,2,3,4.
然后就是232^323,而8-4=4,想要凑出5-7,可以直接使用已经拥有的1-3,分别加4.
至此,初见端倪.
先要凑出2i2^i2i到2i+12^{i+1}2i+1次方的数,需要所有111至2i−12^i-12i−1次方的数.而拥有了所有2i−12^{i-1}2i−1次方的数,就可以凑出2i2^i2i到2i+12^{i+1}2i+1次方的数.
那么从212^121看,我们已经有1至1的数(202^020).那么后续就像多米诺骨牌一样了.
那么也就是说,想凑数[1,n]的所有数,只需要log2nlog_2nlog2 n的数.
那么再把这个(好像是)数学理论的东西搬到C++上,就意味着
在一些情况下,只需要O(log2n)O(log_2n)O(log2 n)的时间复杂度,就可以解决O(n)O(n)O(n)时间复杂度的问题.
即线性->对数.
而且可以从上述的推论中发现,倍增其实跟二进制有点关系.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
ST表
*上方的描述都是在网上搜查得出的结论,下方的描述将会参考深入浅出程序设计竞赛(进阶篇)
ST表是运用倍增思想求取区间最值的算法.
题目:平衡的队列
想求一个序列A中,AiA_iAi 到AjA_jAj 最大值与最小值的差.(有q组问题,序列有n个数.1≤n≤5∗104,1≤q≤1.8∗105)1\le n\le 5*10^4,1\le q \le 1.8*10^5)1≤n≤5∗104,1≤q≤1.8∗105)
因为不可能直接求最大值与最小值的差,就将问题分解称分别求最大值和最小值.
最直接的做法是暴力枚举,但是时间复杂度为O(nq)O(nq)O(nq),不太可行.
效率低下的原因是询问的区间可能有大幅重叠.这些大幅重叠会产生大幅重复.
如果可以通过预处理得道一些小区间的最大值和最小值,再通过这些区间拼凑每一个区间,就可以提高效率.
那么就是这些"小区间"的选择了.
提到预处理,或许可以想到前缀和与差分:预处理前缀和数组可以随意拼出任意区间的和.
但是区间最值可能不行.为什么?
前缀和:
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表算法使用了倍增的思想.
倍增是种什么思想?对数相互连接,形成线性的桥梁.
人话就是你需要nnn个过程才能解出答案,而倍增可以只有log2nlog_2nlog2 n个过程,却可以解出正确的答案(考试时并不提倡,因为可能会扣过程分).
