Overview
A Sparse Table preprocesses an array into overlapping intervals of different sizes. Each table entry stores the result of an operation over a specific interval. For suitable idempotent operations, such as minimum and maximum, a range query can be answered in O(1) time after preprocessing.
How it works
Level zero stores the original array values.; Each higher level combines two smaller intervals to create an interval twice as long.; The interval lengths are powers of two: 1, 2, 4, 8, and so on.; A query determines the largest power of two that fits within the requested range.; For minimum queries, two overlapping intervals can cover the requested range, and their minimum values are combined.
Key concepts
Static arrays; Power-of-two intervals; Preprocessing; Idempotent operations; Range minimum queries; Binary logarithms
Time complexity
operation: Preprocessing; complexity: O(n log n); operation: Range Minimum Query; complexity: O(1); operation: Range Query for Sum; complexity: O(log n) using a decomposition into disjoint power-of-two intervals
Space complexity
O(n log n).
Example
array: 7; 2; query: Find the minimum value in the range [1, 4].; rangeValues: 2; 9; calculation: min(min(2, 9), min(4, 1)) = 1; result: 1
Applications
Range minimum queries; Range maximum queries; Static array analysis; Lowest common ancestor solutions using Euler tours; Competitive programming