Дерево отрезков — различия между версиями
(→Общая идея) |
(→Общая идея) |
||
| Строка 3: | Строка 3: | ||
Очень похоже на sparse table - хотим предподсчитывать какие-то значения для отрезков, и обновлять их при изменении дерева.<br> | Очень похоже на sparse table - хотим предподсчитывать какие-то значения для отрезков, и обновлять их при изменении дерева.<br> | ||
''Замечание: рассматриваем на примере задачи RMQ из конспекта про sparse table'' | ''Замечание: рассматриваем на примере задачи RMQ из конспекта про sparse table'' | ||
| + | |||
| + | == Структура == | ||
| + | На нижнем уровне располагаются элементы массива, на уровень выше - узлы, в которых минимум из двух элементов, на уровень выше - минимум из соответствующих соседей предыдущего уровня и так далее. Рисунок для случая, когда количество элементов в массиве - степень двойки. (vis. 18:54) | ||
Версия 14:02, 8 апреля 2020
Общая идея
Очень похоже на sparse table - хотим предподсчитывать какие-то значения для отрезков, и обновлять их при изменении дерева.
Замечание: рассматриваем на примере задачи RMQ из конспекта про sparse table
Структура
На нижнем уровне располагаются элементы массива, на уровень выше - узлы, в которых минимум из двух элементов, на уровень выше - минимум из соответствующих соседей предыдущего уровня и так далее. Рисунок для случая, когда количество элементов в массиве - степень двойки. (vis. 18:54)
