Дерево отрезков — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива.
Пусть наш массив имеет элементов: . Выберем такое, что . Тогда для хранения дерева отрезков понадобится массив из элементов. В ячейке при будет храниться число , где — функция, которую мы хотим вычислять от отрезков массива. Наиболее часто в качестве берутся функции суммы, произведения, минимумы и максимумы.
Рекурсивное дерево отрезков требует массив из 4 * N элементов для массива из N элементов.
Ниже приведён код функции build построения дерева отрезков для массива α на массиве d для функции суммы на языке С++.
void build(int v, int l, int r) { if (l == r){ d[v] = a[l]; } else { int mid = (l + r) / 2; build(v * 2, l, mid); build(v * 2 + 1, mid + 1, r); d[v] = d[v * 2] + d[v * 2 + 1]; } }
Пусть мы изменили значение . Тогда нам нужно присвоить элементу значение . После чего нужно обновить значения , и.т.д. Таким образом, на изменение элемента уйдёт действий.
Код на С++ для изменения элемента в дереве отрезков для суммы:
void upd(int v, int l, int r, int pos, int val) { if (l == r){ d[v] = val; a[l] = val; } else { int mid = (l + r) / 2; if (pos <= mid){ upd(v * 2, l, mid, pos, val); } else { upd(v * 2 + 1, mid + 1, r, pos, val); } d[v] = d[v * 2] + d[v * 2 + 1]; } }
Для подсчёта функции от элементов используется следующая рекурсивная процедура от аргументов . Здесь — элемент массива , в котором находится значение функции для отрезка , а — отрезок, на котором мы хотим посчитать функцию.
Если и , то ответ равен .
Если , то ответ равен .
Если , то ответ равен .
Иначе отрезок можно разбить на два отрезка: и . Тогда ответом будет .
Таким образом, вычисление функции на отрезке сводится к вычислению функции от элементов массива , соответствующих некоторым отрезкам . Можно показать, что при вычислении функции будет произведено рекурсивных вызовов.
Ниже представлен код для вычисления суммы на отрезке на языке С++:
int get(int v, int l, int r, int ql, int qr) // ql и qr есть границы искомого отрезка { if (l > qr || r < ql){ return 0; } if (ql <= l && r <= qr){ return d[v]; } int mid = (l + r) / 2; return get(v * 2, l, mid, ql, qr) + get(v * 2 + 1, mid + 1, r, ql, qr); }
Предположим, что мы хотим изменить значение не одной ячейки массива , а целого интервала (например, увеличить значения всех ячеек из интервала на заданное число ). Тогда хранения только массива недостаточно. Однако деревья отрезков, способные вычислять сумму и максимум, можно реализовать с хранением двух массивов одинаковой длины и рекурсивной реализацией операции изменения.
Будем хранить массивы и с той же адресацией, что и массив (см. выше). Операция изменения будет состоять в увеличении значения всех ячеек от до на число . может быть как положительным, так и отрицательным.
имеет аргументы . Здесь — номер ячейки в массивах и , в которой хранится информация об отрезке , а — отрезок, на котором производится изменение.
В первую очередь при рекурсивном вызове увеличиваем на .
Далее, если и , то увеличиваем на .
Если , то вызываем рекурсивно .
Если , то вызываем .
Иначе разбиваем отрезок на два: и . Производим 2 рекурсивных вызова и .
Процедура вычисления суммы на отрезке модифицируется аналогично.
Если и , то значение суммы равно .
Если , то значение равно .
Если , то значение равно .
Иначе возвращаем .
Общая сложность операций modify и count составляет .
Аналогично предыдущему случаю будем хранить массивы и . Операция будет иметь тот же смысл и те же аргументы.
Если и , то увеличиваем значения и на .
Если , то вызываем рекурсивно .
Если , то вызываем .
Иначе разбиваем отрезок на два: и . Производим 2 рекурсивных вызова и .
После рекурсивных вызовов (одного или двух), если они имели место, полагаем .
Осталось привести процедуру count вычисления максимума на отрезке.
Если и , то значение максимума равно .
Если , то значение равно .
Если , то значение равно .
Иначе значение максимума равно .
Общая сложность операций modify и count, как и в случае суммы, составляет .
Также задачу RMQ можно решать с помощью Sparse table. Эта структура данных позволяет находить максимум/минимум на отрезке за O(1) с препроцессингом за время O(n log n).
Препроцессинг:
Обозначим — максимум/минимум на отрезке от до . Массив можно заполнить динамически следующим образом:
1) ;
2) или соответственно.
Вычисление:
Ответ на отрезке равен (соответственно ), где lg — максимальная степень двойки, не превосходящая .
Пример:
Рассматриваем диапазон от 1 до 5. Максимальная степень двойки, которая помещается на него, это два, но она не покрывает весь диапазон, а только часть от 1 до 4. Максимум на этом отрезке можно получить, сравнив значения f[1,2] и f[2,2] (максимумы на отрезках от 1 до 4 и от 2 до 5).
Для такого решения достаточно свести задачу RMQ к задаче LCA, построив декартово дерево из элементов вида , то есть - ключ, - приоритет. Приоритеты должны быть упорядочены снизу вверх, то есть в корне должен стоять элемент с наименьшим . Очевидно, такое дерево легко построить за , так как все ключи у нас упорядочены (это идущие друг за другом индексы элементов массива).
После этого ответом на любой запрос будет LCA двух вершин и . Индекс LCA будет лежать в , так как декартово дерево по ключу - двоичное дерево. Благодаря тому, что декартово дерево - пирамида по приоритету, эта же вершина будет иметь наименьший приоритет (значение элемента) из всех, находящихся в
Для задачи LCA известны несколько возможных решений за с препроцессингом и памятью . Такое решение является асимптотически оптимальным.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .