Range queries - sparse table

Sparse table is a data structure for range queries. It can answer queries for associative range functions in O(log n) time and for non-associative range funcions (i.e. min(a,b)) in O(1) time.

The intuition behind sparse table is that any non-negative number can be uniquely represented as a sum of decreasing powers of two. For example, the number 7 represented in binary as 0111 can be written as 2² + 2¹ + 2⁰. In a similar fashion, an interval can also be represented as union of intervals that are decreasing power of 2.

For example, the interval [2, 9) can be represented as [2, 2+2²) U [6, 6 + 2¹) U [8, 8 + 2⁰)

    (2, 9) = [2, 6) + [6, 8) + [8, 9)

The union will contain at most ceil(log2(length of interval)) intervals. In the above example, total intervals = ceil(log(2+9-1)) = ceil(log(10))

The idea behind sparse table is to compute all the range values for intervals which are power of 2 and then combine them to get the actual results.

Creating sparse table

Sparse table stores values in 2D array where each row belongs to an interval. For an array with size N the largest power of 2 that can fit in the length can be computed as P=floor(log2(N)) + 1.

Let’s take the following example to understand how sparse table is created.

We have an array of size N=7, using the formula mentioned above the no. of rows = 3. The sparse table is represented by a 2D array, row 0 contains the original array.

For all other rows, we check the interval and then pick the value from previous row at current index and current index + interval and apply combination function before storing it in current row.

row 1 represents the interval 2¹, the power of 2 is the interval value (1 in this case). For (i,j) = (1,0), we pick (i - 1)(j) = (0,0) and (i-1)(j+interval)=(0,1).

Similarly, for (2, 0), the values at (2-1,0) and (2-1, 0+2) are picked and combination function is applied before storing the values at current index.

Query min of range from table

Let’s get the min value in range (2,5) in the example. First this we have to find the maximum power of 2 this interval can represent, the will floor(log2(r-l+1)). Once the row (interval) is determined, then we can look for the range using the following formula

    min = minOf(talbe[row][left], table[row][right - 2^row + 1])

For the range (2,5), we will get row=2 and minOf(table[2][2], table[2][2]) which is 1.

• Example

import kotlin.math.*

//sampleStart
fun main() {
    // click + to see full script
    val arr = intArrayOf(2, 1, 5, 4, 8, 1, 7).toTypedArray()
    val rows = log(arr.size.toDouble(), 2.0).toInt()
    val minTable = createSparseTable(arr) { a, b -> minOf(a, b) }
    val sumTable = createSparseTable(arr) { a, b -> a + b }

    println("arr = ${arr.contentToString()}")

    (4..6).also {
        println("min of $it = ${getMin(minTable, it)}")
    }
    (2..4).also {
        println("sum of $it = ${getSum(sumTable, rows, it)}")
    }
}
//sampleEnd

fun getMin(table: Array<Array<Int>>, range: IntRange): Int {
    val l = range.first
     val right = range.last
    val i = log((right - l + 1).toDouble(), 2.0).toInt()
    return min(table[i][l], table[i][right.minus(1.shl(i)).plus(1)])
}

fun getSum(table: Array<Array<Int>>, k: Int, range: IntRange): Int {
    var sum = 0
    var left = range.first
    val right = range.last
    for(i in k downTo 0) {
        if ((1.shl(i)) <= (right - left + 1)) {
            sum += table[i][left]
            left += 1.shl(i)
        }
    }
    return sum
}

fun createSparseTable(arr: Array<Int>, f: (a: Int, b: Int) -> Int): Array<Array<Int>> {
    val columns = arr.size
    val rows = floor(log(columns.toDouble(), 2.0)).toInt().plus(1)
    val table = Array(rows) { Array(columns) { 0 } }
    System.arraycopy(arr, 0, table[0], 0, arr.size)
    for (row in 1..rows) {
        var column = 0
         while (column.plus(1.shl(row)) <= columns) {
            table[row][column] = f.invoke(
                 table[row - 1][column],
                table[row - 1][column + (1.shl(row - 1))]
            )
            column++
        }
    }
    return table
}