当前位置: 首页 > news >正文

倍增法

引入

对于任意的整数n,都可以将他拆分为有限个二次幂的和(即二进制拆分)。

那么我们就可以将规模为n的大问题拆分为许多区间长度为二的幂次的小问题。

这样,如何快速解决区间长度为二的幂次的问题就是我们想关心的。

这就是倍增法想解决的问题。

倍增法快速幂

倍增法快速幂的解决的经典问题就是求a^x(mod p)

分析

我们将x二进制拆分为 x0+x1+x2+...+xn,其中xi为二的幂次

现在我们关心如何快速求出a(2i),将上式记为fi,显然fi=f(i-1) * f(i-1)。

现在我们有一个朴素的想法:

f0=1,f1=a;
for i:=1 to [log x]
|	fi=f(i-1) * f(i-1);
end;
ans:=1;
for i:=1 to [log x]
| 	if 2^i存在于x的二进制拆分序列{xi}中
|	|ans=ans*fi;
|	end
end;
print(ans);

现在我们的问题是如何快速判断 \(2^i\)是否存在于{xi}中。其实这并不困难,利用位运算,只需(x^(1<<i))为1即可说明 \(2^i\) 在{xi}中。
我们容易将完整代码给出。

问题

给出一个数组a,q次询问,每次输入l,r,输出al-ar中的最大值。

我们已经介绍了如何拆分长度为x的区间问题。我们来看怎么预处理出长度为2^i 的区间最值。

设fi,p 表示以 p 为左端点,长度为2i 的区间的最大值。

由2^i =2×(2^i−1) 这个式子。长度为 2^i 的区间可以拆成两个长度为2i−1 小区间,第一个区间的端点为p,第二个区间的端点为p+2i−1。
于是得到递推式:fi,p=max(fi−1,p,fi−1,p+2i−1)。

像这样预处理f数组后,我们可以像引言中介绍的那样将问题进行二进制拆分,每次询问的时间复杂度为O(log n)。
能不能做到更快?

不难注意到,如果两个区间有重合是不影响最终结果的,于是对于区间[l,r]最值,我们可以返回以l为左端点的区间最值和以r为右端点的区间最值的max作为回答。
这样 时间复杂度就被降低到了O(1)。

硬是要总结

本文介绍算法思想的核心是将规模为n的问题通过二进制拆分为一个个小问题,通过快速解决小问题以达到解决大问题。

http://www.hskmm.com/?act=detail&tid=31862

相关文章:

  • 复杂版式与印章干扰下的高精度社会团体法人登记证书识别技术
  • 征程 6 | BPU trace 简介与实操
  • 2025年预应力千斤顶厂家最新权威推荐榜:批发采购、张拉设备、同步顶升系统专业供应商综合测评与选购指南
  • 2025.10.15训练记录
  • 利用Next.js中间件漏洞实现SSRF攻击与RCE
  • 三级医疗服务体系 (Three Tiers of Care)
  • 2025年瑕疵检测设备厂家最新推荐排行榜,表面瑕疵检测,薄膜瑕疵检测,铝箔瑕疵在线检测,外观瑕疵检测机公司推荐!
  • 2025年冷却塔厂家最新推荐排行榜:高效制冷与稳定性能之选!
  • 牛客2025秋季算法编程训练联赛1
  • 2025 年风淋室厂家选哪家?广州灵洁凭技术专利与全链服务打造净化设备优质之选
  • 251015读书报告
  • MySQL
  • 元推理框架的诞生,是绝对真实的证明,彻底击溃虚无论
  • JAVA8 map flatmap用法
  • Spring bean初始化过程
  • 吴恩达深度学习课程一:神经网络和深度学习 第二周:神经网络基础 课后习题和代码实践
  • 【Windows】如何管理电脑磁盘文件,保持简洁 - 教程
  • 范围综述
  • 低代码软件开发流程
  • 生成器
  • CSP-S模拟30
  • 2025多校冲刺CSP模拟赛5
  • float
  • 读书报告和代码
  • P66实训2
  • 《程序员的修炼之道:从小工到专家》阅读笔记
  • 关于Pytorch深度学习神经网络的读书报告
  • 牛客刷题-Day13
  • 蛋白表达标签:提升重组蛋白研究与生产的关键工具
  • const int *p和int *const p快速区分