WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

Дерево отрезковструктура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива.

Дерево отрезков в памяти

Пусть наш массив имеет элементов: . Выберем такое, что . Тогда для хранения дерева отрезков понадобится массив из элементов. В ячейке при будет храниться число , где — функция, которую мы хотим вычислять от отрезков массива. Наиболее часто в качестве берутся функции суммы, произведения, минимумы и максимумы.

Рекурсивное дерево отрезков требует массив из 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);
}

Дерево отрезков с модификацией на интервале

Предположим, что мы хотим изменить значение не одной ячейки массива , а целого интервала (например, увеличить значения всех ячеек из интервала на заданное число ). Тогда хранения только массива недостаточно. Однако деревья отрезков, способные вычислять сумму и максимум, можно реализовать с хранением двух массивов одинаковой длины и рекурсивной реализацией операции изменения.

Дерево отрезков для суммы (RSQ)

Будем хранить массивы и с той же адресацией, что и массив (см. выше). Операция изменения будет состоять в увеличении значения всех ячеек от до на число . может быть как положительным, так и отрицательным.

имеет аргументы . Здесь — номер ячейки в массивах и , в которой хранится информация об отрезке , а — отрезок, на котором производится изменение.

В первую очередь при рекурсивном вызове увеличиваем на .

Далее, если и , то увеличиваем на .

Если , то вызываем рекурсивно .

Если , то вызываем .

Иначе разбиваем отрезок на два: и . Производим 2 рекурсивных вызова и .

Процедура вычисления суммы на отрезке модифицируется аналогично.

Если и , то значение суммы равно .

Если , то значение равно .

Если , то значение равно .

Иначе возвращаем .

Общая сложность операций modify и count составляет .

Дерево отрезков для максимума (RMQ)

Аналогично предыдущему случаю будем хранить массивы и . Операция будет иметь тот же смысл и те же аргументы.

Если и , то увеличиваем значения и на .

Если , то вызываем рекурсивно .

Если , то вызываем .

Иначе разбиваем отрезок на два: и . Производим 2 рекурсивных вызова и .

После рекурсивных вызовов (одного или двух), если они имели место, полагаем .

Осталось привести процедуру count вычисления максимума на отрезке.

Если и , то значение максимума равно .

Если , то значение равно .

Если , то значение равно .

Иначе значение максимума равно .

Общая сложность операций modify и count, как и в случае суммы, составляет .

Решение RMQ с помощью Sparse Table

Также задачу 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).

Решение за O(1) с препроцессингом и памятью O(N)

Для такого решения достаточно свести задачу RMQ к задаче LCA, построив декартово дерево из элементов вида , то есть - ключ, - приоритет. Приоритеты должны быть упорядочены снизу вверх, то есть в корне должен стоять элемент с наименьшим . Очевидно, такое дерево легко построить за , так как все ключи у нас упорядочены (это идущие друг за другом индексы элементов массива).

После этого ответом на любой запрос будет LCA двух вершин и . Индекс LCA будет лежать в , так как декартово дерево по ключу - двоичное дерево. Благодаря тому, что декартово дерево - пирамида по приоритету, эта же вершина будет иметь наименьший приоритет (значение элемента) из всех, находящихся в

Для задачи LCA известны несколько возможных решений за с препроцессингом и памятью . Такое решение является асимптотически оптимальным.

Ссылки

См. также

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии