148
правок
Изменения
Новая страница: «== Определение == '''Корневая эвристика (Sqrt-декомпозиция)''' — это метод, или структура данных,…»
== Определение ==
'''Корневая эвристика (Sqrt-декомпозиция)''' — это метод, или структура данных, которая позволяет выполнять некоторые типичные операции (суммирование элементов подмассива, нахождение минимума/максимума и т.д.) за <tex> O(\sqrt n)</tex>.
== Описание ==
''Привидем описание для операции суммирования''
Дан массив <tex>A[0 \ldots n-1]</tex>. Cделаем следующий предпосчёт: разделим массив A на блоки длины <tex>\sqrt{n}</tex> (округлённому к целому), и в каждом блоке заранее предпосчитаем нужную операцию в нём. Пусть len — это длина блока <tex>(len \approx \sqrt{n})</tex>, а <tex>cnt = \left\lceil \frac{n}{len} \right\rceil</tex> — количество блоков:
[[Файл:Корневая эвристика.png]]
Через <tex>b_k</tex> мы обозначили результат предпосчёта в k-ом подотрезке.
Для того чтобы посчитать сумму в отрезке <tex>[l \ldots r]</tex>, надо просуммировать элементы только в двух "хвостах": <tex>[l \ldots (k+1)len-1]</tex> и <tex>[(p+1)len \ldots r]</tex>, и просуммировать значения <tex>b_i</tex> во всех блоках, начиная с k и заканчивая p:
<tex>\sum_{i = l}^r a_i = \sum_{i = l}^{(k + 1)len - 1} + a_i \sum_{i = k}^p b_i + \sum_{i = p + 1}^r a_i</tex>
Размер каждого из "хвостов", очевидно, не превосходит длины блока <tex>len</tex>, а количество блоков не превосходит <tex>cnt</tex>. Поскольку и <tex>len</tex>, и <tex>cnt</tex> мы выбирали <tex>\approx \sqrt{n}</tex>, то всего для вычисления суммы в отрезке <tex>[l \ldots r]</tex> нам понадобится <tex>O(\sqrt{n})</tex> операций.
==Источники==
[http://www.e-maxx.ru/algo/sqrt_decomposition Maximal:: algo:: Sqrt - декомпозиция]
'''Корневая эвристика (Sqrt-декомпозиция)''' — это метод, или структура данных, которая позволяет выполнять некоторые типичные операции (суммирование элементов подмассива, нахождение минимума/максимума и т.д.) за <tex> O(\sqrt n)</tex>.
== Описание ==
''Привидем описание для операции суммирования''
Дан массив <tex>A[0 \ldots n-1]</tex>. Cделаем следующий предпосчёт: разделим массив A на блоки длины <tex>\sqrt{n}</tex> (округлённому к целому), и в каждом блоке заранее предпосчитаем нужную операцию в нём. Пусть len — это длина блока <tex>(len \approx \sqrt{n})</tex>, а <tex>cnt = \left\lceil \frac{n}{len} \right\rceil</tex> — количество блоков:
[[Файл:Корневая эвристика.png]]
Через <tex>b_k</tex> мы обозначили результат предпосчёта в k-ом подотрезке.
Для того чтобы посчитать сумму в отрезке <tex>[l \ldots r]</tex>, надо просуммировать элементы только в двух "хвостах": <tex>[l \ldots (k+1)len-1]</tex> и <tex>[(p+1)len \ldots r]</tex>, и просуммировать значения <tex>b_i</tex> во всех блоках, начиная с k и заканчивая p:
<tex>\sum_{i = l}^r a_i = \sum_{i = l}^{(k + 1)len - 1} + a_i \sum_{i = k}^p b_i + \sum_{i = p + 1}^r a_i</tex>
Размер каждого из "хвостов", очевидно, не превосходит длины блока <tex>len</tex>, а количество блоков не превосходит <tex>cnt</tex>. Поскольку и <tex>len</tex>, и <tex>cnt</tex> мы выбирали <tex>\approx \sqrt{n}</tex>, то всего для вычисления суммы в отрезке <tex>[l \ldots r]</tex> нам понадобится <tex>O(\sqrt{n})</tex> операций.
==Источники==
[http://www.e-maxx.ru/algo/sqrt_decomposition Maximal:: algo:: Sqrt - декомпозиция]
