report VI VI EN
Register | Login
  • HOME
  • PROBLEMSET
  • ROADMAP
  • COMPETITION
  • TOPIC
  • RANKING
  • GUIDE
  • MASHUP
  • ABOUT
  • CONTACT
Module Sparse table

Sparse table

**Frequency: 2/10** Apart from its use in the Lowest Common Ancestor (LCA) problem, sparse tables are primarily employed for the following purposes: - It can be used as a replacement for a Segment Tree in problems where there are no updates, resulting in improved time complexity. - It is also utilized for binary lifting operations. It's worth noting that the time complexity of `log2()` function in C++ is logarithmic, so pre-calculating the logarithm values is a smart move to optimize performance.

Resources

- [CP Algorithms: Sparse Table](https://cp-algorithms.com/data_structures/sparse-table.html#range-minimum-queries-rmq) - [USACO: Binary Jumping](https://usaco.guide/plat/binary-jump?lang=cpp)

Problems

Minimum query 435 / 474 1300
Graph query 307 / 324 1500
GCD 259 / 277 1700
Leaky roof 138 / 172 1800

Graph

  • Shortest path
  • 0-1 BFS / Dial's algorithm
  • Multisource BFS / Dijkstra
  • DAG / Topological sort

Data structure

  • Introduction to Segment Tree and Binary Indexed Tree
  • Sparse table
  • Monotonic queue

Tree

  • Lowest common ancestor (LCA)
  • Euler tour

Dynamic Programming

  • Bitmask DP
  • Exchange labels DP
  • Game DP

Math

  • Introduction to combinatorics
  • Inclusion-exclusion principle