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