Дерево отрезков

Дерево отрезков — структура данных, позволяющая находить значение некоторой ассоциативной функции $f$ на произвольном отрезке $a[i],a[i+1],\dots ,a[j]$ массива за асимптотику $O(\log n)$. Наиболее часто в качестве $f$ берутся функции суммы, произведения, максимум и минимум.

Описание структуры

Дерево отрезков представляет собой корневое дерево, листьями которого являются элементы исходного массива, а другие вершины имеют по 2 ребенка. Каждой вершине в соответствие поставлен интервал, являющийся объединением интервалов ее детей (если у вершины есть дети), либо интервал, содержащий конкретный элемент массива (для листьев). Кроме того, для каждой вершины хранится значение некоторой ассоциативной функции $f$ на данном интервале. Данное дерево будет иметь логарифмическую высоту, так как количество уровней не будет превышать $\log _{2}n$

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

Пусть наш массив $a$ имеет $n$ элементов: $a[0],a[1],\dots ,a[n-1]$.

Выберем $h$ такое, что $2^{h}\geq n$. Дополним наш массив справа нейтральными элементами так, чтобы его длина равнялась $2^{h}$. Тогда для хранения дерева отрезков, построенного на элементах массива $a$, нам понадобится массив $b$ из $2^{h+1}$ ячеек.

Нулевую ячейку в массиве $b$ мы использовать не будем, а ячейки с первой по $(2^{h+1}-1)$-ю будут соответствовать вершинам двоичного дерева с соответствующими номерами. Обычно используется нумерация вершин дерева отрезков в порядке обхода в ширину, то есть корень дерева имеет номер 1, а левый и правый сыновья вершины с номером $v$ имеют номера $2v$ и $2v+1$ соответственно. При такой нумерации вершина с номером $2^{k}+u$ при $0\leq u<2^{k}$ будет соответствовать отрезку $[u2^{h-k};(u+1)2^{h-k}-1]$, то есть в ячейке $b[2^{k}+u]$ будет храниться число $f(a[u2^{h-k}],a[u2^{h-k}+1],\dots ,a[(u+1)2^{h-k}-1])$.

Далее в статье будет использоваться именно такая нумерация вершин дерева отрезков. В качестве альтернативы можно нумеровать вершины в порядке обхода в глубину, тогда левый и правый сыновья вершины $v$ будут иметь номера $v+1$ и $v+2(\lfloor {\dfrac {L+R}{2}}\rfloor -L+1)$, где $[L;R]$ — отрезок, соответствующий вершине $v$. При этом, если строить дерево отрезков сразу по исходному массиву $a$, а не расширять его до длины $2^{h}$ (в таком дереве не все длины отрезков будут степенями двойки и не все листья будут расположены на максимальной глубине), то для его хранения будет достаточно всего $2n$ ячеек в массиве $b$. При хранении же дерева, вершины которого занумерованы в порядке обхода в ширину, длина массива $b$ может достигать $4n-4$.

Построение дерева отрезков

Ниже приведён код на C++ рекурсивной функции $\mathop {\rm {build}}$ построения дерева отрезков для суммы на элементах массива $a$. Сложность построения дерева составляет $O(2^{h})=O(n)$ действий.

void build()
{
    build(1, 0, (1 << h) - 1);
}

void build(int v, int L, int R)
{
    if (L == R){
        b[v] = a[L];
    }
    else {
        int C = (L + R) / 2;
        build(v * 2, L, C);
        build(v * 2 + 1, C + 1, R);
        b[v] = b[v * 2] + b[v * 2 + 1];
    }
}

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

Изменение элемента

Пусть мы изменили значение $a[i]$. Тогда нам нужно обновить значения в ячейках $b[2^{h}+i]$, $b[2^{h-1}+i/2]$, $b[2^{h-2}+i/4]$,..., $b[1]$. Таким образом, на изменение элемента уйдёт $O(h)=O(\log(n))$ действий.

Ниже приведён код на C++ рекурсивной процедуры $\mathop {\rm {update}}$ обновления дерева отрезков для суммы при изменении $i$-го элемента в исходном массиве $a$.

void update(int i, int newValue)
{
    update(1, 0, (1 << h) - 1, i, newValue);
}

void update(int v, int L, int R, int i, int newValue)
{
    if (L == R){
        b[v] = newValue; 
        a[i] = newValue;
    }
    else {
        int C = (L + R) / 2;
        if (i <= C){
            update(v * 2, L, C, i, newValue);
        }
        else {
            update(v * 2 + 1, C + 1, R, i, newValue);
        }
        b[v] = b[v * 2] + b[v * 2 + 1];
    }
}

Подсчёт функции для отрезка

Для подсчёта функции $f$ от элементов $a[l],a[l+1],\cdots ,a[r]$ используется следующая рекурсивная функция $\mathop {\rm {count}}$ от аргументов $v,L,R,l,r$, вычисляющая значение функции $f$ для отрезка $[L;R]\cap [l;r]$. Здесь $v$ — такая вершина дерева, что в ячейке $b[v]$ находится значение функции $f$ для отрезка $[L;R]$.

Если отрезки $[L;R]$ и $[l;r]$ не пересекаются, то ответ равен нейтральному элементу для функции $f$ (0 для суммы, 1 для произведения, $-\infty$ для максимума, $+\infty$ для минимума).

Если $[L;R]\subset [l;r]$, то ответ равен $b[v]$.

Иначе разобьём отрезок $[L;R]$ пополам, положив $C=\lfloor {\dfrac {L+R}{2}}\rfloor$. Сведём задачу к вычислению функции $f$ для отрезков $[L;C]\cap [l;r]$ и $[C+1;R]\cap [l;r]$. Тогда ответ равен $f({\rm {count}}(2v,L,C,l,r),{\rm {count}}(2v+1,C+1,R,l,r))$.

Таким образом, вычисление функции на отрезке $[l;r]$ сводится к вычислению функции от элементов массива $b$, соответствующих некоторым отрезкам $[2^{k}u;2^{k}(u+1)-1]$.

Покажем, что при вычислении функции будет произведено получение $2\log(n)$ результатов. На каждой глубине мы вернём значение не более чем из двух вершин дерева. От противного, положим, что их не менее трёх. Но тогда два вызова из двух соседних вершин могли быть заменены на один вызов из их общего родителя. Следовательно, на каждой глубине мы вернём не более двух значений. Из-за построения высота дерева не превосходит $\log(n)$. Следовательно, будет совершено не более $2\log(n)$ возвратов.

Аналогичными рассуждениями показывается, что за один запрос в дереве мы обойдём не более $4\log(n)$ вершин.

Ниже представлен код на C++ для вычисления суммы на отрезке $[l;r]$.

int getSum(int l, int r)
{
    return getSum(1, 0, (1 << h) - 1, l, r);
}

int getSum(int v, int L, int R, int l, int r)
{
    if (L > r || R < l){
        return 0;
    }
    if (l <= L && R <= r){
        return b[v];
    }
    int C = (L + R) / 2;
    return getSum(v * 2, L, C, l, r) +
            getSum(v * 2 + 1, C + 1, R, l, r);
}

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

Предположим, что мы хотим изменить значение не одной ячейки массива $a$, а целого интервала $a[l],\cdots ,a[r]$ (например, увеличить значения всех ячеек из интервала на заданное число $X$). Тогда хранения только массива $b$ недостаточно. Однако деревья отрезков, способные вычислять сумму и максимум, можно реализовать с хранением двух массивов одинаковой длины и рекурсивной реализацией операции изменения.

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

Будем хранить массивы $sum$ и $add$ с той же адресацией, что и массив $b$ (см. выше).

Рекурсивная процедура ${\rm {modify}}(v,L,R,l,r,X)$ будет состоять в увеличении значения всех элементов на отрезке $[L;R]\cap [l;r]$ на число $X$. $X$ может быть как положительным, так и отрицательным. Здесь $v$ — такая вершина дерева, что в ячейке $sum[v]$ находится сумма всех элементов на отрезке $[L;R]$.

Ниже приведён код процедуры ${\rm {modify}}$ на C++.

void modify(int l, int r, int X)
{
   modify(1, 0, (1 << h) - 1, l, r, X);
}

void modify(int v, int L, int R, int l, int r, int X)
{
   if (L > r || R < l){
       return;
   } 
   if (l <= L && R <= r){
       sum[v] += X * (R - L + 1);
       add[v] += X;
   }
   else {
       int C = (L + R) / 2;
       modify(v * 2, L, C, l, r, X);
       modify(v * 2 + 1, C + 1, R, l, r, X);
       sum[v] = sum[v * 2] + sum[v * 2 + 1] + add[v] * (R - L + 1);
   }
}

Рекурсивная функция ${\rm {getSum}}$ вычисления суммы на отрезке $[L;R]\cap [l;r]$ модифицируется следующим образом. У неё появляется ещё один аргумент $additive$, характеризующий, на сколько нужно увеличить все числа на отрезке $[L;R]$ при подсчёте суммы.

int getSum(int l, int r)
{
   return getSum(1, 0, (1 << h) - 1, l, r, 0);
}

int getSum(int v, int L, int R, int l, int r, int additive)
{
   if (L > r || R < l){
       return 0;
   }
   if (l <= L && R <= r){
       return sum[v] + additive * (R - L + 1);
   }
   int C = (L + R) / 2;
   return getSum(v * 2, L, C, l, r, additive + add[v])
           + getSum(v * 2 + 1, C + 1, R, l, r, additive + add[v]);
}

Cложность операций ${\rm {modify}}$ и ${\rm {count}}$ составляет $O(\log(n))$.

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

Аналогично предыдущему случаю будем хранить массивы $max$ и $add$. Процедура ${\rm {modify}}$ будет иметь тот же смысл и те же аргументы.

void modify(int l, int r, int X)
{
   modify(1, 0, (1 << h) - 1, l, r, X);
}

void modify(int v, int L, int R, int l, int r, int X)
{
   if (L > r || R < l){
       return;
   }
   if (l <= L && R <= r){
       max[v] += X;
       add[v] += X;
   }
   else {
       int C = (L + R) / 2;
       modify(v * 2, L, C, l, r, X);
       modify(v * 2 + 1, C + 1, R, l, r, X);
       max[v] = std::max(max[v * 2], max[v * 2 + 1]) + add[v];
   }
}

Рекурсивная функция ${\rm {getMax}}$ вычисления максимума на отрезке $[L;R]\cap [l;r]$ реализуется аналогично функции ${\rm {getSum}}$ дерева отрезков для суммы.

int getMax(int l, int r)
{
   return getMax(1, 0, (1 << h) - 1, l, r, 0);
}

int getMax(int v, int L, int R, int l, int r, int additive)
{
   if (L > r || R < l){
       return -INF; // Минус бесконечность, т.е. число, которое заведомо меньше любых чисел на нашем отрезке. Например, если все числа неотрицательны, то можно положить INF = 0.
   }
   if (l <= L && R <= r){
       return max[v] + additive;
   }
   int C = (L + R) / 2;
   int max1 = getMax(v * 2, L, C, l, r, additive + add[v]);
   int max2 = getMax(v * 2 + 1, C + 1, R, l, r, additive + add[v]);
   return std::max(max1, max2);
}

Сложность операций ${\rm {modify}}$ и ${\rm {getMax}}$ составляет $O(\log(n))$.

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

Также задачу RMQ можно решать с помощью Sparse table. Эта структура данных позволяет находить максимум/минимум на отрезке за O(1) с препроцессингом за время O(n log n).

Препроцессинг:

Обозначим $\mathop {\rm {f}} [i,k]$ — максимум/минимум на отрезке от $i$ до $i+2^{k}-1$. Массив $\mathop {\rm {f}} [i,k]$ можно заполнить динамически следующим образом:

1) $\mathop {\rm {f}} [i,0]=a[i]$;

2) $\mathop {\rm {f}} [i,k]=\max(\mathop {\rm {f}} [i,k-1],\mathop {\rm {f}} [i+2^{k-1},k-1])$ или $\mathop {\rm {f}} [i,k]=\min(\mathop {\rm {f}} [i,k-1],\mathop {\rm {f}} [i+2^{k-1},k-1])$ соответственно.

Вычисление:

Ответ на отрезке $[l,r]$ равен $\max(\mathop {\rm {f}} [l,lg],\mathop {\rm {f}} [r-2^{lg}+1,lg])$ (соответственно $\min(\mathop {\rm {f}} [l,lg],\mathop {\rm {f}} [r-2^{lg}+1,lg])$), где lg — максимальная степень двойки, не превосходящая $r-l+1$.

Пример:

Рассматриваем диапазон от 1 до 5. Максимальная степень двойки, которая помещается на него, это два, но она не покрывает весь диапазон, а только часть от 1 до 4. Максимум на этом отрезке можно получить, сравнив значения f[1,2] и f[2,2] (максимумы на отрезках от 1 до 4 и от 2 до 5).

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

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

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

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

Ссылки

• Дерево отрезков, его реализация на C++ и задачи, им решаемые, на сайте e-maxx.ru
• Реализация Дерева отрезков на Java

См. также

• Дерево Фенвика
• Список структур данных (деревья)