Skip to content

Instantly share code, notes, and snippets.

@deniskyashif deniskyashif/rmq-st.cs
Last active Jun 28, 2019

Embed
What would you like to do?
Implementation of Range Minimum Query with Sparse Table.
public class RMQLog
{
private int[] A;
private int[,] sparseTable;
private int[] logTable;
public RMQLog(int[] A)
{
this.PrecomputeSparseTable(A);
}
public int RMQ(int left, int right)
{
var k = this.logTable[right - left + 1];
var leftMinIndex = sparseTable[left, k];
var rightMinIndex = sparseTable[right - (1 << k) + 1, k];
return A[leftMinIndex] <= A[rightMinIndex] ? leftMinIndex : rightMinIndex;
}
void PrecomputeSparseTable(int[] A)
{
var N = A.Length;
this.logTable = new int[N + 1];
this.logTable[0] = -1;
for (int i = 1; i <= N; i++)
this.logTable[i] = this.logTable[i / 2] + 1;
var K = this.logTable[N];
this.sparseTable = new int[N, K + 1];
this.A = A;
// Initial step
for (int i = 0; i < N; i++)
sparseTable[i, 0] = i;
// Iteration
for (int j = 1; j <= K; j++)
{
for (int i = 0; i + (1 << j) <= N; i++)
{
int leftIndex = sparseTable[i, j - 1];
int rightIndex = sparseTable[i + (1 << (j - 1)), j - 1];
sparseTable[i, j] = A[leftIndex] <= A[rightIndex] ? leftIndex : rightIndex;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.