Implementation of Range Minimum Query with Sparse Table.

rmq-st.cs

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;
            }
        }
    }
}