当前位置 博文首页 > luotuoass：实用算法实现-第 9 篇 RMQ问题
RMQ(Range Minimum/Maximum Query)问题，就是对于给定数组，在其下标范围[i, j]内给出的最小值（或最大值，下文都称最小值）的问题。
RMQ和LCA问题可以互相转化，一个对RMQ和LCA问题的总结如下表[i]：
| 算法 | 处理方式 | 复杂度 | 备注 |
| 转化算法 | |||
| LCA =>±1RMQ | N/A | O(n) | 引理1，规模O(n) - O(2n-1) |
| RMQ => LCA-CT | N/A | O(n) | 引理2，规模不变 |
| 朴素算法 | |||
| LCA-Naive | online | O(n^2) - O(1) | 动态规划 |
| RMQ-Naive | online | O(n^2) - O(1) | 直接求解 |
| 经典算法 | |||
| LCA-Tarjan | offline | O(na(n)) | |
| RMQ-ST | online | O(nlogn) - O(1) | |
| 改进算法 | |||
| RMQ-ST-Block | online | O(nloglogn) - O(1) | 将RMQ-ST分段处理 |
| ±1RMQ-ST-Block | online | O(n) - O(1) | 控制RMQ-ST-Block中分段的段种数，得到O(n)算法。 |
| 快速算法 | |||
| RMQ-Fast | online | O(n) - O(1) | RMQ => LCA-CT => ±1RMQ |
| 折衷算法 | |||
| RMQ-IT | online | O(n) - O(logn) | 线段树直接处理 |
| RMQ-CT-Tarjan | offline | O(na(n)) | RMQ => LCA-CT再用LCA-Tarjan解决。 |
