Дерево отрезков — различия между версиями
(→Общая идея) |
(→Общая идея) |
||
| Строка 3: | Строка 3: | ||
Очень похоже на sparse table - хотим предподсчитывать какие-то значения для отрезков, и обновлять их при изменении дерева.<br> | Очень похоже на sparse table - хотим предподсчитывать какие-то значения для отрезков, и обновлять их при изменении дерева.<br> | ||
''Замечание: рассматриваем на примере задачи RMQ из конспекта про sparse table'' | ''Замечание: рассматриваем на примере задачи RMQ из конспекта про sparse table'' | ||
| + | |||
| + | == Структура == | ||
| + | На нижнем уровне располагаются элементы массива, на уровень выше - узлы, в которых минимум из двух элементов, на уровень выше - минимум из соответствующих соседей предыдущего уровня и так далее. Рисунок для случая, когда количество элементов в массиве - степень двойки. (vis. 18:54)<br> | ||
| + | Разумеется, уровней всего O(log n). На i-м уровне, начиная от самого нижнего, n / 2^i элементов. Таким образом, все дерево можно построить (просто сумма членов геометрической прогрессии) за O(n). <br> | ||
| + | |||
| + | |||
| + | == Обработка запроса == | ||
| + | Общая идея: процедура getMin начинает от корня дерева и рекурсивно спускается в те отрезки, которые ее интересуют. Пусть мы находимся в вершине x, которая соответствует полуинтервалу TreeSeg = [L_tree, R_tree), а нам нужен минимум на полуинтервале QuerySeg = [L_q, R_q). Строго говоря, возможны три случая:<br> | ||
| + | 1. TreeSeg < QuerySeg. Тогда необходимо вернуть значение из вершины. <br> | ||
| + | 2. TreeSeg () QuerySeg = (/). Необходимо вернуть какую-то большую константу IntMax, или какой-то флаг, показывающий, что отрезки не пересекаются - чтобы уже "вышестоящий орган" думал над тем, что с этим знанием делать. <br> | ||
| + | 3. TreeSeg () QuerySe != (/). Тогда, разумеется, для обработки запроса необходимо вернуть min (getMin (left_half (x)), getMin (right_half (x))). Заметим, что в силу того что left_half и right_half не пересекаются, мы в будущем сможем решать более сложные задачи с помощью этой же структуры. | ||
== Структура == | == Структура == | ||
На нижнем уровне располагаются элементы массива, на уровень выше - узлы, в которых минимум из двух элементов, на уровень выше - минимум из соответствующих соседей предыдущего уровня и так далее. Рисунок для случая, когда количество элементов в массиве - степень двойки. (vis. 18:54) | На нижнем уровне располагаются элементы массива, на уровень выше - узлы, в которых минимум из двух элементов, на уровень выше - минимум из соответствующих соседей предыдущего уровня и так далее. Рисунок для случая, когда количество элементов в массиве - степень двойки. (vis. 18:54) | ||
Версия 14:23, 8 апреля 2020
Содержание
Общая идея
Очень похоже на sparse table - хотим предподсчитывать какие-то значения для отрезков, и обновлять их при изменении дерева.
Замечание: рассматриваем на примере задачи RMQ из конспекта про sparse table
Структура
На нижнем уровне располагаются элементы массива, на уровень выше - узлы, в которых минимум из двух элементов, на уровень выше - минимум из соответствующих соседей предыдущего уровня и так далее. Рисунок для случая, когда количество элементов в массиве - степень двойки. (vis. 18:54)
Разумеется, уровней всего O(log n). На i-м уровне, начиная от самого нижнего, n / 2^i элементов. Таким образом, все дерево можно построить (просто сумма членов геометрической прогрессии) за O(n).
Обработка запроса
Общая идея: процедура getMin начинает от корня дерева и рекурсивно спускается в те отрезки, которые ее интересуют. Пусть мы находимся в вершине x, которая соответствует полуинтервалу TreeSeg = [L_tree, R_tree), а нам нужен минимум на полуинтервале QuerySeg = [L_q, R_q). Строго говоря, возможны три случая:
1. TreeSeg < QuerySeg. Тогда необходимо вернуть значение из вершины.
2. TreeSeg () QuerySeg = (/). Необходимо вернуть какую-то большую константу IntMax, или какой-то флаг, показывающий, что отрезки не пересекаются - чтобы уже "вышестоящий орган" думал над тем, что с этим знанием делать.
3. TreeSeg () QuerySe != (/). Тогда, разумеется, для обработки запроса необходимо вернуть min (getMin (left_half (x)), getMin (right_half (x))). Заметим, что в силу того что left_half и right_half не пересекаются, мы в будущем сможем решать более сложные задачи с помощью этой же структуры.
Структура
На нижнем уровне располагаются элементы массива, на уровень выше - узлы, в которых минимум из двух элементов, на уровень выше - минимум из соответствующих соседей предыдущего уровня и так далее. Рисунок для случая, когда количество элементов в массиве - степень двойки. (vis. 18:54)
