4817
правок
Нижняя граница для динамической связности: различия между версиями
Перейти к навигации
Перейти к поиску
м
Нижняя граница для динамической связности (посмотреть исходный код)
Версия от 12:05, 18 августа 2025
, 18 август→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
'''delete'''(u, v): удаление ребра (u ,v) из графа; | '''delete'''(u, v): удаление ребра (u ,v) из графа; | ||
'''connected'''(u, v): проверка, находятся ли u и v в одной и той же связной компоненте. | '''connected'''(u, v): проверка, находятся ли u и v в одной и той же [[Связная_компонента_графа|связной компоненте]]. | ||
Пусть <math>m</math> – верхняя граница количества ребер в графе. В данной статье обсуждаются нижние границы клеточного зонда для этой задачи. Обозначим за <math>t_u</math> сложность вставки и удаления, а за <math>t_q</math> – сложность проверки. | Пусть <math>m</math> – верхняя граница количества ребер в графе. В данной статье обсуждаются нижние границы клеточного зонда для этой задачи. Обозначим за <math>t_u</math> сложность операций вставки и удаления, а за <math>t_q</math> – сложность проверки. | ||
'''Задача о частных суммах''' | '''Задача о частных суммах''' | ||
Нижние границы для задачи о динамической связности тесно связаны с нижними границами для другой классической задачи – поддержки частных сумм. Формально, задача состоит в том, чтобы поддерживать массив A[1..n], выполняя следующие операции: | Нижние границы для задачи о динамической связности тесно связаны с нижними границами для другой классической задачи – поддержки частных сумм. Формально, задача состоит в том, чтобы поддерживать массив <math>A[1..n]</math>, выполняя следующие операции: | ||
'''update'''(k, <math>\Delta</math>: обновление <math>A[k] \leftarrow \Delta</math>; | '''update'''(k, <math>\Delta</math>): обновление <math>A[k] \leftarrow \Delta</math>; | ||
'''sum'''(k): возвращает частную сумму <math>\sum^k_{i=1} A[i]</math>. | '''sum'''(k): возвращает частную сумму <math>\sum^k_{i=1} A[i]</math>. | ||
| Строка 26: | Строка 26: | ||
Чтобы полностью сформулировать задачу, будем считать, что элементы <math>A[i]</math> берутся из произвольной группы <math>G</math>, содержащей не менее <math>2^{\delta}</math> элементов. В модели клеточного зонда с b-битными ячейками (клетками) обозначим за <math>t_u^{\Sigma}</math> сложность обновления (update), а за <math>t_q^{\Sigma}</math> – сложность проверки (testsum) | Чтобы полностью сформулировать задачу, будем считать, что элементы <math>A[i]</math> берутся из произвольной группы <math>G</math>, содержащей не менее <math>2^{\delta}</math> элементов. В модели клеточного зонда с b-битными ячейками (клетками) обозначим за <math>t_u^{\Sigma}</math> сложность обновления ('''update'''), а за <math>t_q^{\Sigma}</math> – сложность проверки ('''testsum'''), которая также является нижней границей '''sum'''. | ||