Sparse Table & RMQ (Range Minimum Query)
Errichto Algorithms · 18:42
A sparse table answers range-minimum queries (RMQ) on a static array in O(1) per query after O(n log n) preprocessing. It stores the minimum of every interval whose length is a power of two, then answers any query wit...