sparse table

PPTX 11 стр. 411,9 КБ Бесплатная загрузка

11 стр.

FaylHub.uz

Скачать через Telegram

Размер 411,9 КБ

Тип файла PPTX

Страницы 11

Обновлено Дек 2025

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

1 / 11

sparse table sparse table algorithms and data structures course sparse table sparse table is a data structure, that allows answering range queries. it can answer most range queries in , but its true power is answering range minimum queries (or equivalent range maximum queries). for those queries it can compute the answer in time. the only drawback of this data structure is, that it can only be used on immutable arrays. this means, that the array cannot be changed between two queries. if any element in the array changes, the complete data structure has to be recomputed. algorithms and data structures course sparse table idea any non-negative number can be uniquely represented as a sum of decreasing powers of two. this is just a variant of the binary representation of a number. e.g. . for a number x there can be at most summands. by the same reasoning any interval …

2 / 11

table creation because the range of length splits nicely into the ranges and , both of length , we can generate the table efficiently using dynamic programming: the function will depend on the type of query. for range sum queries it will compute the sum, for range minimum queries it will compute the minimum. the time complexity of the precomputation is . algorithms and data structures course sparse table range sum query: idea. for this type of queries, we want to find the sum of all values in a range. therefore the natural definition of the function is . to answer the sum query for the range , we iterate over all powers of two, starting from the biggest one. as soon as a power of two is smaller or equal to the length of the range , we process the first part of range , and continue with the …

3 / 11

mum query is o(1). algorithms and data structures course image110.png image120.png image48.png image1.png image150.png image2.png image170.png image3.png image190.png image200.png image4.png image220.png image5.png /docprops/thumbnail.jpeg

4 / 11

5 / 11

Хотите читать дальше?

Скачайте все 11 страниц бесплатно через Telegram.

Скачать полный файл

О "sparse table"

sparse table sparse table algorithms and data structures course sparse table sparse table is a data structure, that allows answering range queries. it can answer most range queries in , but its true power is answering range minimum queries (or equivalent range maximum queries). for those queries it can compute the answer in time. the only drawback of this data structure is, that it can only be used on immutable arrays. this means, that the array cannot be changed between two queries. if any element in the array changes, the complete data structure has to be recomputed. algorithms and data structures course sparse table idea any non-negative number can be uniquely represented as a sum of decreasing powers of two. …

Этот файл содержит 11 стр. в формате PPTX (411,9 КБ). Чтобы скачать "sparse table", нажмите кнопку Telegram слева.

Теги: sparse table PPTX 11 стр. Бесплатная загрузка Telegram