Семинар 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}$. [не успели разобрать]