Sparse Tables: Implementing sparse tables for efficient range queries.

Sparse Tables are a powerful data structure for answering range queries efficiently, especially for static array data. They are particularly useful for answering range minimum/maximum queries in logarithmic time after linearithmic preprocessing time. Here's how you can implement a Sparse Table for range minimum queries (RMQ) in Go:

Sparse Table Implementation

1. Preprocessing: Precompute the minimum values for all intervals with sizes that are powers of two.
2. Querying: Use the precomputed values to answer queries in constant time.

Here's a complete implementation in Go:

go
package main

import (
	"fmt"
	
)

// SparseTable structure for Range Minimum Query (RMQ)
type SparseTable struct {
	data  [][]int
	log   []int
	n     int
}

// NewSparseTable initializes the Sparse Table for a given array
func NewSparseTable(arr []int) *SparseTable {
	n := len(arr)
	log := make([]int, n+1)
	log[1] = 0
	for i := 2; i <= n; i++ {
		log[i] = log[i/2] + 1
	}
	k := log[n] + 1

	// Initialize Sparse Table
	data := make([][]int, n)
	for i := range data {
		data[i] = make([]int, k)
		data[i][0] = arr[i]
	}

	// Precompute values for intervals of size 2^j
	for j := 1; j < k; j++ {
		for i := 0; i+(1<<j)-1 < n; i++ {
			data[i][j] = min(data[i][j-1], data[i+(1<<(j-1))][j-1])
		}
	}

	return &SparseTable{data: data, log: log, n: n}
}

// Query returns the minimum value in the range [L, R]
func (st *SparseTable) Query(L, R int) int {
	j := st.log[R-L+1]
	return min(st.data[L][j], st.data[R-(1<<j)+1][j])
}

// Helper function to get minimum of two integers
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	arr := []int{1, 3, -1, 7, 8, 3, 2, 6}
	st := NewSparseTable(arr)
	fmt.Println("Range Minimum Query Results:")
	fmt.Printf("Minimum of range [0, 3]: %d\n", st.Query(0, 3))
	fmt.Printf("Minimum of range [1, 5]: %d\n", st.Query(1, 5))
	fmt.Printf("Minimum of range [2, 6]: %d\n", st.Query(2, 6))
	fmt.Printf("Minimum of range [4, 7]: %d\n", st.Query(4, 7))
}

Explanation

1. Preprocessing:

   • We first compute the logarithm values which help in determining the largest power of 2 that fits within any given range.
   • We initialize a 2D slice data where data[i][j] represents the minimum value in the interval [i, i + 2^j - 1].
   • We fill in the first column of the table with the array values since intervals of size 2^0 are just the individual elements.
   • For each subsequent column j, we fill in the values using the precomputed values from the previous column.

2. Querying:

   • To answer a query for the minimum value in the range [L, R], we use the largest power of 2 that fits within this range.
   • The result is the minimum of the two precomputed intervals that cover the query range.

This implementation ensures that preprocessing the array takes $O(n \log n)$ time, and each query can be answered in $O(1)$ time. This efficiency makes Sparse Tables an excellent choice for static range query problems.