1632
правки
Изменения
м
rollbackEdits.php mass rollback
# Решите за $O(\log{n})$ на запрос. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам на отрезке заданное число и вывести сумму сумм всех подотрезков отрезка.
# Решите за $O(\log{n})$ на запрос. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам на отрезке заданное число, умножить все элементы на отрезке на заданное число, вывести $i$-й элемент массива.
# Модифицировать алгоритм Фараха-Колтона-Бендера, чтобы массив precalc занимал только $O(K \log{K})$ бит памяти для каждой маски.
# Дано взвешенное дерево. Научиться отвечать на запросы "вес пути из $u$ в $v$". После предобработки за $O(n)$ ответ на запрос за $O(1)$.
# Дано взвешенное дерево. Научиться отвечать на запросы "вес пути из $u$ в $v$" и "изменить вес ребра". После предобработки за $O(n)$ ответ на запрос за $O(\log{n})$.
# Дано взвешенное дерево. Научиться отвечать на запросы "вес ребра" и "прибавить ко всем ребрам на пути от $v$ до $u$ число $d$". После предобработки за $O(n)$ ответ на запрос за $O(\log{n})$.
# Алгоритм Хьюи. Дано дерево, вершины которого раскрашены в цвета, то есть задано отображение $col: V \to \{1..k\}$. С помощью LCA найти $dc: V \to \{1..k\}$, где $dc(u)$ - число различных цветов в поддереве с корнем в вершине $u$. Время работы: $O(V)$.
# Задано взвешенное дерево. Посчитать число простых путей в дереве длины от $L$ до $R$ и весом от $x$ до $y$. Время работы $O(n \log^2{n})$.
# Задано невзвешенное дерево. Изначально все вершины белого цвета. Научиться отвечать на запросы: покрасить белую вершину в черную, к заданной вершине найти ближайшую черную вершину. Время работы одного запроса $O(\log{n})$.
# Задано невзвешенное дерево. Изначально все вершины белого цвета. Научиться отвечать на запросы: покрасить белую вершину в черную, покрасить черную вершину в белую, к заданной вершине найти ближайшую черную вершину. Время работы одного запроса $O(\log^2{n})$.
# Покраску дерева в $k$ цветов от 1 до $k$ назовем яркой, если между любыми двумя вершинами одного цвета $c$, существует вершина цвета $d$, что $d < c$. Рассмотрим функцию $f(n) = k$ {{---}} минимальное $k$, что любое дерево из $n$ вершин можно ярко покрасить в $k$ цветов. Докажите, что $f(n) = O(\log{n})$
# Задано дерево из $n$ вершин. В каждой вершине есть число. Нужно отвечать на запросы: медиана в множестве чисел, записанных в вершинах на пути. Время на запрос: $O(\log{n})$.
# Рассмотрим подвешенное дерево. Пусть $s(v)$ {{---}} размер поддерева с корнем в вершине $v$, $C(v)$ {{---}} множество всех непосредственных потомков вершины $v$, $h(v) = \operatorname*{arg\,max}\limits_{u \in C(v)} s(u)$, $f(v) = s(v) - s(h(v))$. Доказать, что $\sum\limits_{v \in V}f(v) = O(n \log{n})$.
# Рассмотрим подвешенное дерево. Пусть $k(v)$ {{---}} высота поддерева с корнем $v$, $C(v)$ {{---}} множество всех непосредственных потомков вершины $v$, $d(v) = \operatorname*{arg\,max}\limits_{u \in C(v)} k(u)$, $g(v) = \sum\limits_{\substack{
u \in C(v) \\
u \ne d(v)}} k(v)$. Доказать, что $\sum\limits_{v \in V}g(v) = O(n)$.
# Задано подвешенное дерево. Нужно отвечать на запросы: подвесить вершину как лист к одной из имеющихся вершин, найти наименьшего общего предка двух уже добавленных вершин. Время работы запросов: $O(n \log{n})$.
# Предложите алгоритм добавления в АВЛ-дерево за $O(h)$, где $h$ {{---}} высота дерева.
# Предложите алгоритм удаления из АВЛ-дерева за $O(h)$, где $h$ {{---}} высота дерева.
# Предложите алгоритм добавления в красно-черное дерево за $O(h)$, где $h$ {{---}} высота дерева.
# Предложите алгоритм удаления из красно-черного дерева за $O(h)$, где $h$ {{---}} высота дерева.
# Статически оптимальное дерево поиска: пусть заданы ключи и известно для каждого ключа, сколько раз его потребуется искать: $p[i]$. Требуется построить дерево поиска, чтобы суммарное время доступа ко всем ключам было минимально.
# Предложите алгоритм слияния двух АВЛ-деревьев, при том, что в первом дереве все ключи меньше, чем во втором за $O(\log n)$
# Предложите алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше или равны заданному $x$, а во втором - больше, за $O(\log n)$
# В АВЛ-дереве находятся вершины с ключами от 1 до $n$. Какие ключи могут быть в корне?
# В красно-черном дереве находятся вершины с ключами от 1 до $n$. Какие ключи могут быть в корне?
# Предложите реализацию АВЛ-дерева, в которой в каждом узле хранится $O(1)$ бит
# Перекошенное сбалансированное дерево. Дерево называется перекошенным сбалансированным, если у каждой вершины разность высоты левого и правого поддерева 0, 1 или 2. Предолжите реализацию операций вставки и удаления для перекошенного сбалансированного дерева.
# Мальчик Петя считает, что если в дереве поиска можно хранить несколько одинаковых ключей, то на пути от одного такого ключа до другого не может быть ключей с другим значением. Тогда можно легко найти все такие ключи. Прав ли он?
# Докажите, что высота красно-черного дерева $O(\log{n})$.
</wikitex>
