✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-212

Sparse Tables

A Sparse Table is a static data structure used to answer range queries efficiently by storing results for intervals whose lengths are powers of two.

Explanation

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

Example or application

Array

  • 7

  • 2

  • 9

  • 4

  • 1

  • 6

Query

Find the minimum value in the range [1, 4].

Range Values

  • 2

  • 9

  • 4

  • 1

Calculation

min(min(2, 9), min(4, 1)) = 1

Result

1

Definition

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.

Preprocessing

Description

Let st[k][i] represent the result for an interval of length 2^k starting at index i.

Recurrence

st[k][i] = min(st[k-1][i], st[k-1][i + 2^(k-1)])

Explanation

Each interval is constructed by combining two adjacent intervals of half its length.

Query Method

Description

For an inclusive range [L, R], calculate k = floor(log2(R - L + 1)). Then combine the two intervals of length 2^k beginning at L and ending at R.

Formula

min(st[k][L], st[k][R - 2^k + 1])

Supported Operations

  • Minimum

  • Maximum

  • Greatest common divisor

Note

The O(1) query method applies to idempotent operations that can safely combine overlapping intervals.

Time Complexity

OperationComplexity

Preprocessing

O(n log n)

Range Minimum Query

O(1)

Range Query for Sum

O(log n) using a decomposition into disjoint power-of-two intervals

Space Complexity

O(n log n).

Key Concepts

  • Static arrays

  • Power-of-two intervals

  • Preprocessing

  • Idempotent operations

  • Range minimum queries

  • Binary logarithms

Advantages

  • Answers suitable range minimum and maximum queries in O(1) time.

  • Does not require a tree traversal during a query.

  • Useful when many queries are performed on unchanged data.

  • The query process is simple after preprocessing.

Limitations

  • Requires O(n log n) memory.

  • Preprocessing takes O(n log n) time.

  • Not suitable for frequent array updates because changes may require rebuilding affected table entries.

  • The overlapping-interval O(1) method does not work for ordinary sum queries.

Applications

  • Range minimum queries

  • Range maximum queries

  • Static array analysis

  • Lowest common ancestor solutions using Euler tours

  • Competitive programming

Related Topics

  • Segment Trees

  • Fenwick Trees

  • Range Minimum Query

  • Binary Logarithms

  • Static Range Queries

Practice Questions

QuestionAnswer

What kind of data is a Sparse Table best suited for?

Static data that receives many range queries but few or no updates.

What interval lengths are stored in a Sparse Table?

Intervals whose lengths are powers of two.

Why can a minimum query take O(1) time?

Two overlapping power-of-two intervals can cover the query range, and minimum is an idempotent operation.

Learning Objectives

  • Explain the central idea and purpose of sparse tables.

  • Identify the assumptions, inputs, and conditions relevant to sparse tables.

  • Evaluate an application of sparse tables for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Advanced Data Structures

Suggest a correction or source · More in Algorithms & Data Structures