RMQ算法时间复杂度
时间: 2024-08-16 13:06:14 浏览: 34
RMQ (Range Minimum Query) 算法,也称为区间最值查询,主要用于数据结构中高效地查找某个区间内的最小值。其中一种常见的实现方法是通过构建一棵自底向上的最小堆(Min Heap)。Huffman's Algorithm 或 Fibonacci Heap 这些数据结构也能用于实现。
线性的预处理时间复杂度是 RMQ 的关键特性。对于长度为 n 的数组,预处理过程通常需要 O(n log n) 时间。之后,对于每个查询区间 [L, R],堆顶元素就是该区间的最小值,查询操作的时间复杂度通常是 O(1),因为只需要从堆顶取出一次值即可。
相关问题
写一段C++语言的实现RMQ算法的代码
抱歉,我不确定您指的是哪种RMQ算法。一般来说,RMQ是“区间最小值查询”(Range Minimum Query)的缩写,其实现算法有多种。以下是两种常见的RMQ算法的实现代码,供参考:
1. 线段树RMQ算法
```python
class SegmentTree:
def __init__(self, arr):
self.tree = [0] * (4 * len(arr))
self.build(arr, 0, 0, len(arr) - 1)
def build(self, arr, index, left, right):
if left == right:
self.tree[index] = arr[left]
else:
mid = (left + right) // 2
self.build(arr, index * 2 + 1, left, mid)
self.build(arr, index * 2 + 2, mid + 1, right)
self.tree[index] = min(self.tree[index * 2 + 1], self.tree[index * 2 + 2])
def query(self, index, left, right, qleft, qright):
if left > qright or right < qleft:
return float('inf')
elif qleft <= left and qright >= right:
return self.tree[index]
else:
mid = (left + right) // 2
return min(self.query(index * 2 + 1, left, mid, qleft, qright),
self.query(index * 2 + 2, mid + 1, right, qleft, qright))
# 示例
arr = [1, 3, 2, 7, 9, 11]
tree = SegmentTree(arr)
print(tree.query(0, 0, len(arr) - 1, 1, 4)) # 输出2,即arr[2:5]的最小值
```
2. ST算法
```python
import math
class ST:
def __init__(self, arr):
n = len(arr)
k = int(math.log2(n))
self.table = [[0] * (k + 1) for _ in range(n)]
for i in range(n):
self.table[i][0] = arr[i]
for j in range(1, k + 1):
for i in range(n - 2 ** j + 1):
self.table[i][j] = min(self.table[i][j - 1], self.table[i + 2 ** (j - 1)][j - 1])
def query(self, left, right):
k = int(math.log2(right - left + 1))
return min(self.table[left][k], self.table[right - 2 ** k + 1][k])
# 示例
arr = [1, 3, 2, 7, 9, 11]
st = ST(arr)
print(st.query(1, 4)) # 输出2,即arr[2:5]的最小值
```
CShap RMQ 源代码
以下是C#实现的RMQ(区间最小值)算法的源代码:
using System;
public class RMQ
{
private int[,] sparseTable;
public RMQ(int[] arr)
{
int n = arr.Length;
int logn = (int)Math.Log(n, 2) + 1;
sparseTable = new int[n, logn];
for (int i = 0; i < n; i++)
{
sparseTable[i, 0] = arr[i];
}
for (int j = 1; j < logn; j++)
{
for (int i = 0; i + (1 << j) - 1 < n; i++)
{
sparseTable[i, j] = Math.Min(sparseTable[i, j - 1], sparseTable[i + (1 << (j - 1)), j - 1]);
}
}
}
public int Query(int l, int r)
{
int k = (int)Math.Log(r - l + 1, 2);
return Math.Min(sparseTable[l, k], sparseTable[r - (1 << k) + 1, k]);
}
}
// 示例用法
int[] arr = { 2, 5, 1, 3, 6, 4 };
RMQ rmq = new RMQ(arr);
Console.WriteLine(rmq.Query(1, 4)); // 输出 1
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)