rmq算法（倍增）

rmq算法，有详细注释 dp1[i][j] = max ( dp1[i][j-1] , dp1[i+(1<<(j-1))][j-1] ) ; dp2[i][j] = min ( dp2[i][j-1] , dp2[i+(1<<(j-1))][j-1] ) ; ### RMQ算法（倍增法） #### 一、引言 RMQ问题（Range Minimum/Maximum Query，区间最小/大值查询）是计算机科学中一个非常基础且重要的问题。其核心在于快速找到数组中某个指定区间内的最大或最小值。在实际应用中，例如在图像处理、生物信息学以及数据库系统等领域都有广泛的应用。倍增法是一种解决RMQ问题的有效策略之一。 #### 二、算法原理与实现 **1. 倍增法的基本思想** 倍增法的核心思路在于预处理出一系列长度为 \(2^k\) 的区间的最大/最小值，这样对于任意一个查询区间 \([l, r]\)，都可以通过将该区间分解成若干个长度为 \(2^k\) 的子区间以及可能的一个额外的“尾巴”区间来求解。具体来说： - 对于每个位置 \(i\) 和长度 \(2^j\)，我们计算出从位置 \(i\) 开始长度为 \(2^j\) 的区间的最大值和最小值。 - 查询时，我们将区间 \([l, r]\) 分解成若干个长度为 \(2^k\) 的子区间，然后取这些子区间最大值中的最大值（或最小值中的最小值）作为最终结果。 **2. 数据结构定义** 根据题目描述，数据结构如下定义： - `dp1[i][j]` 表示从位置 \(i\) 开始长度为 \(2^j\) 的区间的最大值。 - `dp2[i][j]` 表示从位置 \(i\) 开始长度为 \(2^j\) 的区间的最小值。 其中 `dp1` 和 `dp2` 都是二维数组，第一维表示起始位置，第二维表示区间的长度（以 \(2^j\) 形式表示）。 **3. 初始化与预处理** 预处理部分主要包含两个步骤：初始化和区间最大/最小值的计算。 - **初始化**：首先需要确定一个辅助数组 `num` 来存储每个位置对应的最长 \(2^j\) 区间长度。这里的实现是通过 `init()` 函数完成的，其中 `num[i]` 记录了位置 \(i\) 能够构成的最大 \(2^j\) 区间的长度 \(j\)。 - **区间最大/最小值的计算**：这部分是通过 `rmq()` 函数完成的，其主要逻辑是按照 \(j\) 从小到大的顺序依次计算出所有长度为 \(2^j\) 的区间的最大值和最小值，并存入 `dp1` 和 `dp2` 数组中。 **4. 查询** 查询函数 `ask(x, y)` 的目的是返回区间 \([x, y]\) 内的最大值与最小值之差。这个函数利用了预处理的结果来快速响应查询请求。 #### 三、代码分析 **1. 初始化** ```c void init() { int j = 0; for (int i = 1; i <= 50005; i++) { if (i <= (1 << j)) num[i] = j; else num[i] = ++j; } return; } ``` 此函数用于初始化 `num` 数组，记录每个位置对应的最长 \(2^j\) 区间长度。 **2. 区间最大/最小值计算** ```c void rmq(int n) { int i, j; for (j = 1; j <= num[n]; j++) for (i = 1; i < n; i++) { if (i + (1 << j) - 1 > n) break; dp1[i][j] = max(dp1[i][j - 1], dp1[i + (1 << (j - 1))][j - 1]); dp2[i][j] = min(dp2[i][j - 1], dp2[i + (1 << (j - 1))][j - 1]); } return; } ``` 该函数用于计算所有长度为 \(2^j\) 的区间的最大值和最小值，并存入 `dp1` 和 `dp2` 数组。 **3. 查询** ```c int ask(int x, int y) { int i, j; int k; k = num[y - x + 1]; // k = bit(k); return max(dp1[x][k - 1], dp1[y - ((1 << (k - 1)) - 1)][k - 1]) - min(dp2[x][k - 1], dp2[y - ((1 << (k - 1)) - 1)][k - 1]); } ``` 此函数根据预处理的结果，快速计算出区间 \([x, y]\) 内的最大值与最小值之差。 #### 四、总结 倍增法是一种高效的 RMQ 解决方案，它通过对区间进行预处理，大大提高了查询效率。通过本文的分析，我们可以看到倍增法的核心思想、数据结构设计以及具体的实现细节。这种算法不仅适用于解决RMQ问题，还为其他基于区间查询的问题提供了思路和方法。