# 一、倍增与RMQ

## 1. 倍增思想

### (1) 什么是倍增

倍增法（英语：binary lifting），顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。这个方法在很多算法中均有应用，其中最常用的是：RMQ问题和求LCA（最近公共祖先）。

倍增思想是一种十分巧妙的思想，“倍增”二字体现在它每次将当前的已知结果或考察范围扩大一倍。正是由于这个原因，它的时间复杂度降低了很多，一般是将一个系数 $N$ 变为 $\log_2N$。

### (2) 倍增思想举例

**例子1**: 寻找2的幂，体现了倍增的思想。  
如果要求比 $n$ 小的最近的2的幂，可以用 $2^{\lfloor \log_2 n \rfloor}$ 来表示。从1开始跳跃 $\lfloor \log_2 n \rfloor$ 次，就能找到。

**例子2**: 如何用尽可能少的砝码称量出 $[0, 31]$ 之间的所有重量？（只能在天平的一端放砝码）  
答案是使用 1, 2, 4, 8, 16 这五个砝码，可以称量出 $[0, 31]$ 之间的所有重量。每次选择2的整次幂作砝码的重量，就可以使用极少的砝码数量来称量任意所需的重量。可以发现，我们的目标量翻倍时，砝码的数量只需加1。

**例子3**: 有非负整数数列：$a_1, a_2, a_3, \dots, a_n$，有 $M$ 次询问，每次需要求：不超过给定的整数 $T_i$ 的最大前缀和。  
求解思路：预处理前缀和，倍增思想跳跃取值。

## 2. RMQ 问题

**RMQ**（Range Maximum Query），用于求静态区间最大值（也可以求最小值）。  
**ST 表**（Sparse Table, 稀疏表）实现RMQ可以做到：$O(n \log n)$ 的预处理，$O(1)$ 的时间复杂度查询。一般用于多次询问RMQ的问题。特别要注意：ST的算法条件是数组本身不能有修改。  
ST 表是用于**解决可重复贡献问题**的数据结构。

### (1) RMQ的求解思想

以每个点为左端点，求出长度为 $2^{\text{len}}$ 的区间最大值。左端点的选择有 $n$ 种，区间长度的选择有：$1, 2, 4, \dots, 2^{\log_2 n}$，也就是有 $n \log_2 n$ 种需要讨论的状态。这里采用动态规划（DP）与倍增思想来求出从每个点开始的长度为 $2^{\text{len}}$ 的区间最大值。

**第一步**：求 ST 表

一、倍增与RMQ

1. 倍增思想

(1) 什么是倍增

(2) 倍增思想举例

例子1: 寻找2的幂，体现了倍增的思想。
如果要求比 $n$ 小的最近的2的幂，可以用 $2^{\lfloor \log_2 n \rfloor}$ 来表示。从1开始跳跃 $\lfloor \log_2 n \rfloor$ 次，就能找到。

例子2: 如何用尽可能少的砝码称量出 $[0, 31]$ 之间的所有重量？（只能在天平的一端放砝码）
答案是使用 1, 2, 4, 8, 16 这五个砝码，可以称量出 $[0, 31]$ 之间的所有重量。每次选择2的整次幂作砝码的重量，就可以使用极少的砝码数量来称量任意所需的重量。可以发现，我们的目标量翻倍时，砝码的数量只需加1。

例子3: 有非负整数数列：$a_1, a_2, a_3, \dots, a_n$，有 $M$ 次询问，每次需要求：不超过给定的整数 $T_i$ 的最大前缀和。
求解思路：预处理前缀和，倍增思想跳跃取值。

2. RMQ 问题

RMQ（Range Maximum Query），用于求静态区间最大值（也可以求最小值）。
ST 表（Sparse Table, 稀疏表）实现RMQ可以做到：$O(n \log n)$ 的预处理，$O(1)$ 的时间复杂度查询。一般用于多次询问RMQ的问题。特别要注意：ST的算法条件是数组本身不能有修改。
ST 表是用于解决可重复贡献问题的数据结构。

(1) RMQ的求解思想

第一步：求 ST 表

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com