4817
правок
Нижняя граница для динамической связности: различия между версиями
Материал из WEGA
Нижняя граница для динамической связности (посмотреть исходный код)
Версия от 08:34, 18 августа 2025
, 18 август→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Динамические деревья (''Dynamic trees'') == Постановка задачи == Задача о динамической связности требует поддержки структуры графа G следующими операциями: insert(u, v): вставка неориентированного ребра (u, v) в граф; delete(u, v): удаление ребр...») |
Irina (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
Задача о динамической связности требует поддержки структуры графа G следующими операциями: | Задача о динамической связности требует поддержки структуры графа G следующими операциями: | ||
insert(u, v): вставка неориентированного ребра (u, v) в граф; | '''insert'''(u, v): вставка неориентированного ребра (u, v) в граф; | ||
delete(u, v): удаление ребра (u ,v) из графа; | '''delete'''(u, v): удаление ребра (u ,v) из графа; | ||
connected(u | '''connected'''(u, v): проверка, находятся ли u и v в одной и той же связной компоненте. | ||
Пусть m – верхняя граница количества ребер в графе. В данной статье обсуждаются нижние границы клеточного зонда для этой задачи. Обозначим за | Пусть <math>m</math> – верхняя граница количества ребер в графе. В данной статье обсуждаются нижние границы клеточного зонда для этой задачи. Обозначим за <math>t_u</math> сложность вставки и удаления, а за <math>t_q</math> – сложность запроса. | ||
'''Задача о частных суммах''' | '''Задача о частных суммах''' | ||
Нижние границы для задачи о динамической связности тесно связаны с нижними границами для другой классической задачи – поддержки частных сумм. Формально, задача состоит в том, чтобы поддерживать массив A[1 | Нижние границы для задачи о динамической связности тесно связаны с нижними границами для другой классической задачи – поддержки частных сумм. Формально, задача состоит в том, чтобы поддерживать массив A[1..n], выполняя следующие операции: | ||
'''update'''(k, <math>\Delta</math>: обновление <math>A[k] \leftarrow \Delta</math>; | |||
sum(k): возвращает частную сумму | '''sum'''(k): возвращает частную сумму <math>\sum^k_{i=1} A[i]</math>. | ||
testsum(/ | '''testsum'''(k, <math>\sigma</math>): возвращает булево значение, указывающее, верно ли, что <math>sum(k) = \sigma</math>. | ||
