Skip to content
CCC Python Course

Sparse table

Stage
7
Module
M7.3
Lessons
1

In this module

  • Precompute O(N log N) sparse table for O(1) idempotent range queries.
  • Implement sparse table using logarithmic doubling.
  • Optimize queries for min, max, and gcd.

Before this module

M6.12Doubling and binary lifting on sequencesM4.6Number theory I

Lessons

  1. 1Sparse table for fast range queries

Practice

Try this on the judge. The link opens the problem on WMOJ.

  1. 2021 S5
    Math Homework (opens on WMOJ in a new tab) WMOJ

    Verify that every consecutive range has the same GCD.