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

Дерево отрезков — это структура данных, которая поддерживает две основные операции:

• обработку запроса на отрезке;
• обновление одного элемента массива.

С её помощью можно поддерживать суммы на отрезке, минимумы, максимумы и многие другие агрегаты так, чтобы и запрос, и обновление работали за \(O(\log n)\).

По сравнению с деревом Фенвика дерево отрезков более универсально. Дерево Фенвика особенно удобно для сумм, а дерево отрезков подходит и для более общих типов запросов. Цена за эту гибкость — чуть более сложная реализация и больший расход памяти.

Устройство¶

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

Для простоты будем считать, что:

• размер массива равен степени двойки;
• индексация элементов начинается с нуля.

Если длина массива не равна степени двойки, в конец можно дописать фиктивные элементы.

Рассмотрим массив:

7 4 5 2 9 1 6 3
0 1 2 3 4 5 6 7

Построим по нему дерево отрезков для сумм. Тогда листья содержат сами элементы массива, а каждая внутренняя вершина хранит сумму своего левого и правого поддеревьев.

flowchart TD
    n1[37]
    n2[18] --> n1
    n3[19] --> n1
    n4[11] --> n2
    n5[7] --> n2
    n6[10] --> n3
    n7[9] --> n3
    a0[7] --> n4
    a1[4] --> n4
    a2[5] --> n5
    a3[2] --> n5
    a4[9] --> n6
    a5[1] --> n6
    a6[6] --> n7
    a7[3] --> n7

Например:

• вершина со значением \(11\) соответствует отрезку \([0,1]\);
• вершина со значением \(7\) соответствует отрезку \([2,3]\);
• вершина со значением \(18\) соответствует отрезку \([0,3]\);
• корень со значением \(37\) соответствует всему массиву.

Каждая внутренняя вершина покрывает отрезок длины, равной степени двойки.

Как отвечать на запрос суммы¶

Главная идея в том, что любой запрос на отрезке \([a,b]\) можно разбить на \(O(\log n)\) непересекающихся кусков, каждый из которых уже хранится в вершине дерева.

Возьмём отрезок \([2,6]\):

7 4 5 2 9 1 6 3
0 1 2 3 4 5 6 7

Сумма на нём равна:

Этот диапазон удобно разбивается так:

• отрезок \([2,3]\) со значением \(7\);
• отрезок \([4,5]\) со значением \(10\);
• отрезок \([6,6]\) со значением \(6\).

Значит,

Если на каждом уровне дерева брать вершины как можно крупнее, то на одном уровне понадобится не более двух вершин. Поэтому общее число использованных вершин будет равно \(O(\log n)\).

Как выполнять обновление¶

Если значение одного элемента массива изменилось, нужно пересчитать только те вершины, чьи диапазоны содержат этот элемент.

Пусть мы изменили элемент в позиции \(5\). Тогда затронутся только вершины на пути от соответствующего листа к корню:

• лист для позиции \(5\);
• его родитель;
• следующий предок;
• и так далее до корня.

Такой путь содержит \(O(\log n)\) вершин, значит и обновление работает за \(O(\log n)\).

Хранение в массиве¶

Дерево отрезков удобно хранить не указателями, а обычным массивом tree размера 2*n, где n — число элементов исходного массива.

Используется такая нумерация:

• tree[1] — корень;
• tree[2] и tree[3] — его дети;
• tree[4], tree[5], tree[6], tree[7] — следующий уровень;
• элементы tree[n] ... tree[2*n-1] — листья.

Для нашего примера получится такое размещение:

индекс:   1   2   3   4   5   6   7   8  9 10 11 12 13 14 15
значение: 37 18 19 11  7 10  9   7  4  5  2  9  1  6  3

Отсюда сразу следуют связи:

• родитель вершины k находится в k/2;
• левый ребёнок — в 2*k;
• правый ребёнок — в 2*k+1.

Реализация запроса суммы¶

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

int sum(int a, int b) {
    a += n;
    b += n;
    int s = 0;
    while (a <= b) {
        if (a % 2 == 1) s += tree[a++];
        if (b % 2 == 0) s += tree[b--];
        a /= 2;
        b /= 2;
    }
    return s;
}

Как это работает¶

Сначала индексы a и b переносятся в слой листьев. После этого мы постепенно поднимаемся вверх по дереву.

• Если a — правый ребёнок, то его диапазон целиком лежит внутри ответа, поэтому мы добавляем tree[a] и сдвигаем a вправо.
• Если b — левый ребёнок, то его диапазон тоже целиком входит в ответ, поэтому мы добавляем tree[b] и сдвигаем b влево.
• Затем обе границы поднимаются к родителям.

На каждом шаге мы поднимаемся на один уровень вверх, поэтому время работы равно \(O(\log n)\).

Реализация обновления¶

Теперь увеличим значение элемента в позиции k на x.

void add(int k, int x) {
    k += n;
    tree[k] += x;
    for (k /= 2; k >= 1; k /= 2) {
        tree[k] = tree[2*k] + tree[2*k+1];
    }
}

Сначала меняется лист, затем пересчитываются все вершины на пути к корню. Поскольку высота дерева равна \(O(\log n)\), обновление тоже работает за \(O(\log n)\).

Какие ещё запросы можно поддерживать¶

Дерево отрезков полезно не только для сумм. Оно подходит для любой операции, у которой ответ на большом отрезке можно собрать из ответов на двух половинах.

Например:

• минимум;
• максимум;
• наибольший общий делитель;
• побитовое and;
• побитовое or;
• побитовое xor.

Пример с минимумом¶

Пусть массив такой:

7 4 5 2 8 1 6 3

Тогда каждая вершина хранит минимум на своём диапазоне, а не сумму.

flowchart TD
    n1[1]
    n2[2] --> n1
    n3[1] --> n1
    n4[4] --> n2
    n5[2] --> n2
    n6[1] --> n3
    n7[3] --> n3
    a0[7] --> n4
    a1[4] --> n4
    a2[5] --> n5
    a3[2] --> n5
    a4[8] --> n6
    a5[1] --> n6
    a6[6] --> n7
    a7[3] --> n7

Тогда:

• корень хранит минимум всего массива;
• каждая вершина равна минимуму из двух детей;
• запрос и обновление делаются по той же схеме, только вместо сложения используется min.

Поиск позиции с помощью дерева¶

Структура дерева отрезков позволяет не только агрегировать значения на диапазоне, но и искать нужную позицию.

Например, если в вершинах хранятся минимумы, можно за \(O(\log n)\) найти позицию одного из минимальных элементов. Для этого достаточно спускаться от корня вниз:

• сравнить минимум в левом и правом сыне;
• перейти туда, где лежит нужное значение;
• повторять, пока не дойдём до листа.

То есть дерево отрезков — это не просто «быстрые суммы на отрезке», а довольно универсальный каркас для множества задач.

Что важно запомнить¶

• Дерево отрезков поддерживает запрос на отрезке и обновление элемента за \(O(\log n)\).
• В листьях лежат элементы массива, а внутренние вершины агрегируют значения на диапазонах.
• Любой отрезок можно разбить на \(O(\log n)\) узлов дерева.
• После изменения одного элемента пересчитывается только путь от листа к корню.
• Один и тот же шаблон работает не только для сумм, но и для минимума, максимума и других ассоциативных операций.

Небольшое сравнение¶

Дерево отрезков особенно полезно в задачах, где массив изменяется по ходу работы и при этом нужны быстрые ответы на запросы по диапазонам.