Informatik

Was ist eine Sparse Table?

Eine Sparse Table beantwortet statische Bereichsabfragen nach Vorverarbeitung.

Für idempotente Operationen wie Minimum sind Range-Minimum-Queries in $O(1)$ möglich, Updates aber nicht effizient.