Семинар 4. LCA и RMQ

Разбор прошлого домашнего задания

Задача 1. Роман Чулков

Задача 2. Эмиль Рахимов

Задача 4. Денис Рахманкин

Задачи с практики

1. Дано подвешенное дерево на \(n\) вершинах. Постройте за \(\mathcal O(n\log n)\) структуру данных, которая за \(\mathcal O(\log n)\) отвечает на запрос \(\mathrm{up}(u,k)\): найти предка \(u\), расстояние до которого равно \(k\).

2. Дано подвешенное дерево на \(n\) вершинах, на каждом ребре написано число. Постройте за \(\mathcal O(n\log n)\) структуру данных, которая за \(\mathcal O(\log n)\) отвечает на запрос \(\mathrm{path\_min}(u,v)\): найти минимум на пути от \(u\) до \(v\).

3. Дана полугруппа \((X,\otimes)\) и подвешенное дерево на \(n\) вершинах, на каждом ребре написан элемент \(X\); операции над элементами полугруппы занимают \(\mathcal O(1)\) памяти и времени. Постройте за \(\mathcal O(n\log n)\) структуру данных, которая за \(\mathcal O(\log n)\) отвечает на запрос \(\mathrm{path\_prod}(u,v)\): найти тензорное произведение элементов на всех рёбрах пути от \(u\) до \(v\) (взятых именно в том порядке, в котором они лежат на пути).

4. Дано подвешенное дерево на \(n\) вершинах, на каждом ребре написано положительное число — длина ребра. Постройте за \(\mathcal O(n\log n)\) структуру данных, которая за \(\mathcal O(\log n)\) отвечает на запрос \(\mathrm{path\_mid}(u,v)\): определить вершину или ребро, где находится середина пути (в метрическом смысле) от \(u\) до \(v\).

5. Сведите RMQ к LCA. Формально, дан массив \(\left\{a_i\right\}\) из \(n\) целых чисел, постройте за \(\mathcal O(n)\) структуру данных, использующую алгоритм Фараха-Колтона, Бендера, которая за \(\mathcal O(1)\) отвечает на запрос \(\min(\ell,r)\): найти минимум в массиве от \(a_\ell\) до \(a_{r-1}\). [не успели разобрать]