Нижняя граница для динамической связности: различия между версиями

Заметим, что это совпадает с хрестоматийной верхней границей при использовании дополненных деревьев. Можно построить сбалансированное бинарное дерево над <math>A[1], ..., A[n]</math> и хранить в каждом внутреннем узле сумму его поддерева. Тогда обновления и запросы затрагивают <math>O(lg \; n)</math> узлов (и тратят <math>O(\lceil \delta\b \rceil)</math> времени в каждом из них из-за размера группы). Чтобы уменьшить время запросов, можно использовать [[B-Дерево|B-дерево]].

Чтобы реализовать операцию '''update'''(x, <math>\pi</math>), сначала удаляются все ребра между столбцами x и x + 1, а затем вставляются новые ребра согласно <math>\pi</math>. Это дает <math>t_u^{\Sigma} = O(2n \cdot t_u)</math>. Для реализации операции '''testsum'''(x, <math>\pi</math>) можно использовать <math>n</math> запросов '''connected''' между парами точек <math>(1, у) \rightsquigarrow (х + 1, \pi(у))</math>. Тогда <math>t_q^{\Sigma} = O(n \cdot t_q)</math>. Заметим, что запрос '''sum''' не может быть реализован так же просто. Динамическая связность является основным мотивом для изучения запроса '''testsum'''.