Range Sum Query in Linear Time

rsq-st.cs

public class RSQLog
{
    private int[] A;
    private int[,] sparseTable;
    private int[] logTable;

    public RSQLog(int[] A)
    {
        this.PrecomputeSparseTable(A);
    }

    public int RSQ(int left, int right)
    {
        var sum = 0;
        // The size of the second dimension
        var K = sparseTable.GetLength(1); 

        for (int j = K; j >= 0; j--)
        {
            if ((1 << j) <= (right - left + 1))
            {
                sum += this.sparseTable[left, j];
                left += 1 << j;
            }
        }

        return sum;
    }

    private 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] = A[i];

        // Iteration
        for (int j = 1; j <= K; j++)
        {
            for (int i = 0; i + (1 << j) <= N; i++)
            {
                int left = sparseTable[i, j - 1];
                int right = sparseTable[i + (1 << (j - 1)), j - 1];
                sparseTable[i, j] = left + right;
            }
        }
    }
}