Given a sequence of static values of length N, a data structure where the preprocessing O(NlogN) allows operations on the upper interval of the sequence to be computed in O(1)

Conditions required for operation - associative law :

  • Unit and inverse yuan are not required.

There is no need to use this for operations with inverse roots, such as addition. - Because we can do the same thing with construction O(N) using cumulative sum, we can do the same thing with construction O(N).

Cumulative product from left to right” can be used to achieve obsolete rule prohibiting match-ups between wrestlers from the same group of stables, e.g., by multiplying without inverses.

  • The Disjoint Sparse Table allows the user to compute the product of arbitrary intervals by combining a large number of cumulative products.

Poem on Disjoint Sparse Table and Seg Trees - noshi91’s note

Sparse Table


This page is auto-translated from [/nishio/Disjoint Sparse Table](https://scrapbox.io/nishio/Disjoint Sparse Table) using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.