112
правок
Изменения
м
→Обобщение на большие размерности
Можно заметить, что возможно реализовать и D-мерную разреженную таблицу за <tex>O((N\log(n))^{D})</tex> памяти и <tex>O((N\log(n))^{D})</tex> времени на построение, где ответ на запрос, например, <tex> \mathrm {RMQ(l, r)} </tex> будет выполняться за <tex> O(D) </tex>.
''Способ построение'': Если в данном случае, для того, чтобы построить двумерную структуру мы сначала должны были построить одномерную, то также и в случае с D-мерной структуре - сначала нужно построить (D-1)-мерную, а из нее получить D-мерную, поэтому и получаем такую асимптотику на построение.
''Ответ на запрос'': Абсолютно аналогичен рассмотренному здесь, только обобщается до размерности D.
----
При помощи 2D Sparse Table можно решать и некоторые другие задачи, например, поиск суммы, произведения элементов подматрицы.
== См. также ==
