4817
правок
Нижняя граница для динамической связности: различия между версиями
Материал из WEGA
Нижняя граница для динамической связности (посмотреть исходный код)
Версия от 09:01, 18 августа 2025
, 18 август→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 35: | Строка 35: | ||
Заметим, что это совпадает с хрестоматийной верхней границей при использовании дополненных деревьев. Можно построить сбалансированное бинарное дерево над A[1] | Заметим, что это совпадает с хрестоматийной верхней границей при использовании дополненных деревьев. Можно построить сбалансированное бинарное дерево над <math>A[1], ..., A[n]</math> и хранить в каждом внутреннем узле сумму его поддерева. Тогда обновления и запросы затрагивают <math>O(lg \; n)</math> узлов (и тратят <math>O(\lceil \delta\b \rceil)</math> времени в каждом из них из-за размера группы). Чтобы уменьшить время запросов, можно использовать [[B-Дерево|B-дерево]]. | ||
'''Связь с динамической связностью''' | '''Связь с динамической связностью''' | ||
Теперь поясним, как из нижних границ для поддержания частных сумм следуют нижние границы для динамической связности. Рассмотрим задачу о частных суммах над группой G = | Теперь поясним, как из нижних границ для поддержания частных сумм следуют нижние границы для [[Полностью_динамическая_связность:_верхняя_и_нижняя_границы|динамической связности]]. Рассмотрим задачу о частных суммах над группой <math>G = S_n</math>, то есть группой перестановок на <math>n</math> элементах. Заметим, что <math>\delta = lg(n!) = \Omega(n \; lg \; n)</math>. Стандартно задается <math>b = \Theta(lg \; n)</math>, так как это естественный размер слова, используемый в верхних границах для динамической связности. Отсюда следует, что <math>t_q^{\Sigma} lg(t_u^{\Sigma}/t_q^{\Sigma}) = \Omega(n \; lg \; n)</math>. | ||
