倍增
本页面将简要介绍倍增法。
定义
倍增法(英语:binary lifting),顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理,大大地优化时间复杂度。
这个方法在很多算法中均有应用,其中最常用的是 RMQ 问题和求 LCA(最近公共祖先)。
应用
RMQ 问题
参见:RMQ 专题
RMQ 是 Range Maximum/Minimum Query 的缩写,表示区间最大(最小)值。使用倍增思想解决 RMQ 问题的方法是 ST 表。
树上倍增求 LCA
参见:最近公共祖先
例题
题 1
例题
如何用尽可能少的砝码称量出
解题思路
答案是使用 1 2 4 8 16 这五个砝码,可以称量出
为什么说是极少呢?因为如果我们要量出
题 2
例题
给出一个长度为
数据范围:
解题思路
这里显然不能暴力模拟跳
所以就需要进行一些预处理,提前整合一些信息,以便于在查询的时候更快得出结果。如果记录下来每一个可能的跳跃次数的结果的话,不论是时间还是空间都难以承受。
那么应该如何预处理呢?看看第一道例题。有思路了吗?
回到本题。我们要预处理一些信息,然后用预处理的信息尽量快的整合出答案。同时预处理的信息也不能太多。所以可以预处理出以 2 的整次幂为单位的信息,这样的话在预处理的时候只需要处理少量信息,在整合的时候也不需要大费周章。
在这题上,就是我们预处理出从每个点开始跳 1、2、4、8 等等步之后的结果(所处点和点权和),然后如果要跳 13 步,只需要跳 1+4+8 步就好了。也就是说先在起始点跳 1 步,然后再在跳了之后的终点跳 4 步,再接着跳 8 步,同时统计一下预先处理好的点权和,就可以知道跳 13 步的点权和了。
对于每一个点开始的 go[i][x]
表示第 sum[i][x]
表示第 sum[i][x] = sum[i-1][x]+sum[i-1][go[i-1][x]]
,且 go[i][x] = go[i-1][go[i-1][x]]
。
当然还有一些实现细节需要注意。为了保证统计的时候不重不漏,我们一般预处理出「左闭右开」的点权和。亦即,对于跳 1 步的情况,我们只记录该点的点权和;对于跳 2 步的情况,我们只记录该点及其下一个点的点权和。相当于总是不将终点的点权和计入 sum。这样在预处理的时候,只需要将两部分的点权和直接相加就可以了,不需要担心第一段的终点和第二段的起点会被重复计算。
这题的
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
|
本页面最近更新:2024/10/9 22:38:42,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:NachtgeistW, H-J-Granger, Ir1d, orzAtalod, Backl1ght, CCXXXI, countercurrent-time, dkz051, Enter-tainer, Fomalhauthmj, Great-designer, hsfzLZH1, iamtwz, leoleoasd, Lewy Zeng, Marcythm, MingqiHuang, opsiff, ouuan, PeterlitsZo, ShadowsEpic, siger-young, sshwy, SukkaW, Tiphereth-A, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用