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

Подмассивы

Предположим у нас есть массив из 8-ми элементов с индексами от 0 до 7. Значения массива могут быть любыми, но для простоты пусть это будут целые числа.

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

Также довольно частой задачей является найти значение функции не на всем массиве, а на некотором подмассиве. Например, найти сумму на отрезке [2, 6] (индексация начинается с нуля, так что фактически это сумма элементов array[1] + array[2] + ... + array[5]), ответ которого будет 2 + 5 + 1 + 4 + 9 = 21, или наименьший элемент на отрезке [4, 8], который равен 1 (значение с индексом 3).

Вычислить подобные значения не состовляет труда, но есть одно но - все эти вычисления требуют времени O(n), так как время зависит от количества элементов. Желание улучшить время работы вычисления подобных функций привело к появлению различных структур данных, которые позволили вычислять значения за время О(Nlog(N)), O(log(N)) и даже за O(1) для некоторых конкретных функций.

Мы коротко пройдемся по основным из них и после перейдем непосредственно к дереву отрезков т.к. эта структура данных как раз позволяет найти ассоциативную функцию за время O(log(n)), но потратив в ~2 раза больше памяти.

Префиксные суммы

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

У нас есть 8 значений массива. Чему равна сумма из массива, в котором ноль элементов? Очевидно она равно нулю. А если у нас есть только 1 элемент сумма равна этому элементу. Каждый раз, когда мы будем добавлять следующий элемент, сумма массива будет равна сумме прошлых элементов + сам этот элемент. Например, когда у нас есть только элемент 7 - сумма равна 7. Добавив элемент 2 сумма равна 9. Добавив 5 сумма равна 14 и т.д.

Найдем сумму для всех значений от 0 до размера массива. Мы получим следующие значения

Красным цветом обозначенны суммы для каждого элемента. Их будет n + 1, т.к. первый элемент говорит о сумме элементов когда размер равен 0. Теперь мы можем сказать за константное время сумму любого диапазона от первого элемента до j. Например, сумма [1, 5] = 19.

Если мы хотим найти сумму подмассива [i, j], где i не первый элемент, то нам нужно сначала найти значение суммы на подмассиве [1, j], а затем вычесть из него [1, i] (не путаем что первый элемент имеет индекс 0, а в запросе обычно указывается позиция, т.е. первый элемент имеет позицию 1). Визуально для запроса [3, 5] это выглядит так.

формула для нахождения массива сум sumArray массива array выглядит так: sumArray[i + 1] = sumArray[i] + array[i]

Подобные префиксные суммы можно найти и для двух, трехмерных массивов.

Обратимость

Префиксные суммы позволяют нам найти сумму подмассива за время О(1). Но можно ли также найти, например наибольшее/наименьшее значение?

Ответ на этот вопрос - нет. И дело здесь в таком понятии, как обратимость. У некоторых функций есть обратные функции, которые позволяют вернуться к начальному значению. В случае со сложением обратная функция - это вычитание. Если мы сначала прибавим к числу X некоторое значение A, а потом вычтем его то получим снова X (X + A - A = X).

Именно поэтому мы могли сначала найти сумму от первого элемента до нужной границы, а потом вычесть те элементы, которые не должны быть в сумме.

Для минимума / максимума такой обратной функции нет, а значит префиксные суммы нам не подходят.

Вопрос, а можно ли вместа операции сложения выполнять операцию умножения, ведь для нее есть обратная операция деления? Тут стоит учитывать что значение числа может быть 0, тогда произведение всего будет равно 0 и помнить, что при перемножении мы можем быстро выйти за границу числового типа. Так что короткий ответ - да, но не всегда.

RMQ

RMQ (Range minimum query) - это запрос минимума (также можно найти и максимум) на отрезке. Это не структура данных, это задача которую можно решить разными способами. Довольно популярными решениями являются разреженная таблица (Sparse table) и дерево отрезков.

Разреженная таблица

Мы можем найти для каждого элемента минимум для этого элемента и всех оставльных элементов. Такой подсчет требует времени и места порядка O(N ^ 2). Для простоты приведем массив из 6-х элеметов: 7, 4, 2, 9, 1, 5.

Теперь найдем минимум для всех возможных вариантов и заапишем в таблицу. Теперь мы можем отвечать на запросы минимума/максимума за время O(1), просто перейдя по нужной строке/столбцу (например, для отрезка [2, 4] результат будет на пересечении строки 2 и столбца 4, где написано значение 2). Понятный минус такого способа - занимаемая память.

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

Минимумом для 1-го элемента является сам элемент. Сначала запишем сами элементы. Затем найдем минимум для 2-х соседних элементов. Затем для 4-х и т.д. каждый раз удваивая отрезок. Всего таких рассчетов должно быть log(N) + 1, т.е. в нашем случае их будет 3 - для 1-го элемента, для 2-х и 4-х. Например, значение 1 в строке k = 2 и i = 2 (со значением 1) говорит о том, что из 4-х элементов (2, 9, 1, 5) минимумом является 1. В итоге мы получим следующую таблицу.

В дальнейшем min(i, j) можно найти как min(ST(i, j), ST(j - 2 ^ k + 1, k)), где k = log((j - i + 1)). Оставим эту формулу в покое, но основная идея - у нас есть отрезок, который всегда можно покрыть 2-мя отрезками поменьше. На примере ниже минимум серого отрезка можно найти как минимум из отрезка А и В. Если отрезки пересекаются - ничего страшного, т.к. операция нахождения минимума идемпотентна (она всегда вернет один и тот же минимум на одних данных, вне зависимости от количества запросов. С суммой так не получится).

Преподсчет

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

Таким образом, временную сложность алгоритма можно поделить на 2 стадии - время на препроцессинг/преподсчет и время на непосредственно запрос.

В случае с префиксными суммами мы вычисляли суммы и записывали эти суммы для в новый массив. Это и был преподсчет. Он нужен для того, чтобы сложность запроса в дальнейшем была О(1). Время на подсчет зависит от длинны массива, ведь нам нужно сложить все элементы. Поэтому время преподсчета О(N).

Статическая и динамическая постановка задачи

Возьмем для примера наш прошлый массив и подсчитаем для него префиксные суммы. Но что будет, если теперь мы захотим часто менять значения начального массива. Например, значение 1 на позиции 2 сменилось на 15. Это означает, что все дальнейшие суммы, начиная с элемента на позиции 2, будут неверны и их нужно опять пересчитать, что займет в среднем О(N) времени.

Но ведь и простой подсчет суммы перебором занимает О(N) времени. Зачем нам тогда нужны префиксные суммы, если мы не изменили сложность.

Таким образом, структуры дынных можно разделить на статические (static) и динамические (dynamic). Префиксные суммы - это статическая структура данных, если вам нужно находить быстро суммы на подмассиве и массив не меняется - это идеальная структура данных. Но если значения меняются часто - вам нужно после каждого изменения вновь пересчитывать все суммы, как следствие такая структура данных не дает особых преимуществ.

Дерево отрезков, наоборот - динамическая структура данных. В ней изменение элемента выполняется за время O(log(N)) и поиск значения функции на подмассиве также за O(log(N)). Почему это так разберем чуть позже.

Offline и online постановка задачи

Еще один способ разбить структуры данных - это offline и online режим.

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

Online режим предпологает, что нам дается 1 запрос и мы отдаем 1 ответ. Все запросы обрабатываются последовательно.

Ассоциативная функция

Дерево отрезков позволяет быстро найти значение некоторой ассоциативной функции. Для начала разберем, что такое ассоциативная функция. Это функция, обладающая ассоциативным свойством, т.е. если у нас есть операция вида А op B op C, где вместо op - любой оператор (+, -, / и т.д.), то мы можем записать как (A op B) op C и как A op (B op C), и общий результат не именится.

Сложение ассоциативно, т.к. (А + В) + С = А+ (В + С), но вычитание - нет, т.к. (А - В) - С != А- (В - С)

Каким еще операции могут быть ассоциативными? Классическими примерами являются операции суммы, наибольшего / наименьшего значения, логического И, ИЛИ, НОК и НОД, перемножения, исключающего или, конкатенации (объединения строк, не меняя их порядок).

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

Итак переходим непосредственно к дереву отрезков, или Segment tree. Напомню массив, который у нас есть.

Мы напишем реализацию такой структуры данных, которая с одной стороны вычисляет некоторую функцию для любого подмассива за O(log(N)), а с другой стороны способна именить любое значение за время O(log(N)).

Как понятно из названия, эта структура представляет дерево. Давайте подсчитаем сумму для каждых 2-х соседних элементов, и напишем ее выше. Потом для каждой пары сделаем тоже самое, пока количество элементов не станет равно 1.

В итоге у нас получится следующее дерево.

Если мы посмотрим на конкретный узел в этом дереве, то он представляет сумму на определенном подмассиве. Например, число 9 - это сумма элементов с индексами 0 и 1, число 15 - это сумма элементов массива с 0 по 3 включительно и т.д. Корневой элемент (39) представляет сумму всего массива.

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

Однако мы нашли не все возможные подсуммы. Возьмем для примера слудеющий подмассив начиная с позиции 1 и заканчивая позицией 8. Там есть 7 элементов, которые нужно сложить. Мы можем представить сумму элементов как i1 + i2 + i3 + i4 + i5 + i6 + i7, или как i2 + (i2 + i3) + (i4 + i5 + i6 + i7), а суммы (i2 + i3) и (i4 + i5 + i6 + i7) у нас уже подсчитанны (в зеленых кружках).

Здесь должно быть понятно требование к ассоциативности, ведь мы считаем элементы не всегда в том порядке, в котором считали бы их при обычном сложении перебором. Мы разбиваем большой отрезок на несколько поменьше, для которых уже известна сумма.

Представление дерева

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

В случае со ссылочным представлением мы создаем класс примерно следующего вида, и связываем ссылки.

В случае массива все немного интереснее. Давайте пронумеруем все вершины по принципу поиска в ширину, начиная с корня и пусть корень будет иметь индекс 1.

Мы заметим несколько интересных особенностей.

Во-первых, количество не листовых узлов (т.е. узлов, которые представляют сумму хотя бы 2-х элементов) равно точно N - 1 (опять же, при условии что количество N степень двойки. В данном случае N = 8).

Во-вторых, между родителем и дочерними узлами есть зависимость. Если родитель имеет индекс i, то каждый левый ребенок имеет индекс 2 * i, а каждый правый ребенок индекс 2 * i + 1. (В случае, если мы начинаем индексирование корневого элемента с 0, то левый ребенок имеет формулу 2 * i + 1, а правый 2 * i + 2). Например, для элемента со значением 9 и индексом 4 левый ребенок имеет индекс 8, а правый - 9.

В-третьих, родителя любого элемента можно найти целочисленным (без остатка) делением на 2. Из примера выше 8 / 2 = 4, и 9 / 2 = 4. Так мы можем перейти от родителя к любому из детей и обратно, таким образом спускаясь или поднимаясь по дереву.

И последнее, левый ребенок всегда имеет четный индекс, а правый - нечетный. Это особенности не дерева отрезков, а бинарного дерева, на котором основано дерево отрезков.

Как теперь мы можем хранить дерево? Мы выделяем массив, который в 2 раза больше тех данных, что нам приходят. Во вторую половину мы записываем эти значения, а в первую половину мы записываем суммы двух дочерних узлов (которые уже будут посчитаны) по формуле array[i] = array[i * 2] + array[i * 2 + 1].

Таким образом мы получим заполненный массив с подсчитанными суммами следующего вида. Значение по индесу 0 не используется.

Мы реализуем дерево отрезков на языке Java. За структуру будет отвечать класс SegmentTree. Главные параметры - это размер массива поступающих данных и сам массив хранения всех данных. Метод build сначала заполняет вторую половину теми значениями, которые мы получили, а затем высчитываем все узлы дерева.

Нейтральный элемент

В этом примере есть одно упрощение - мы заранее договоримся что размер values будет степенью 2. В жизни это может быть не так. Т.к. бинарное дерево хорошо работает именно с числами со степенью 2, то самый простой способ будет дополнить все остающие значения нейтральными элементами до седующей степени 2. например, если у нас есть 9 элементов, то последние 7 будут нейтральными элементами.

Что такое нейтральный элемент? Для большинства функций есть такое значение операнда, который не изменит результат. Для суммы это ноль. При сложении любого числа с 0 мы получим это число. Для умножения это 1, т.к. умножение на 1 не изменяет число. Для нахождения наименьшего значения нейтральный элемент будет Максимально возможное значение (Integer.MAX_VALUE или что то подобное).

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

Научимся обновлять значения. Можно заметить, что для этого нужно обновить только всех родителей узла, который мы обновляем. Для этого мы переходим к родителю (поделив индекс на 2), после чего высчитываем новое значение родителя, и переходим к родителю родителя, пока не дойдем до корневого узла.

Метод установки нового значения принимает позицию (индекс будет на 1 меньше, поэтому при вычислении i мы вычитаем 1) и новое значение. Продолжаем это делать, пока не дойдем до предкорневого узла. В этот момент i будет равен или 2, или 3. Мы заходим в цикл последний раз, i становится равным 1, обновляем корень и в следующей итерации условие цикла будет ложным.

В данном случае мы начали с нижнего элемента и использовали цикл, но можно начать с корня и использовать рекурсию. Тогда мы переходим или в левый, или в правый узел и рекурсивно переходим в нем в левый/правый узел в зависимости от позиции. Когда рекурсия дойдет до конца, но обратном пути обновляем значения узлов суммы на каждом уровне.

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

Фундаментальный элемент и фундаментальный отрезок.

Для начала введем понятие фундаментального элемента и фундаментального отрезка. Каждый не листовой узел представляет из себя фундаментальный элемент, который представляет фундаментальный отрезок. Например, корневой узел (элемент) представляет сумму на всем подмассиве (отрезок).

Попробуем найти сумму на некотором подмассиве, изображенном ниже. Это подмассив с позициями [2, 6]

Можно заметить, что каждый узел может быть одним из 3-х типов:

• Для данного узла и левый, и правый ребенок должен быть включен в итоговую сумму. Для такой ситуации нам нет смысла идти на уровень ниже, ведь мы уже подсчитали сумму этих элементов заранее (узел со значением 6). Обозначим такие узлы зеленым цветом.
• Для данного узла и левый, и правый ребенок не должны быть включены в итоговую сумму. Для такой ситуации нам также нет смысла идти глубже, т.к. эти элементы нам не нужны (узел со значением 11). Обозначим такие узлы красным цветом.
• Узел, у которого один ребенок нужно включить в итоговую сумму, а другой нет (узел со значением 9 или 24). Обозначим такой узел желтым цветом.

В итоге мы получим следующее дерево. Когда узел желтый - мы переходим к его детям. Если узел зеленый - мы добавляем сумму к общему результату и выходим. Если узел красный - мы просто выходим, эти узлы нам не нужны. Осталось понять, как определить цвет.

Каждый узел представляет свой фундаментальный отрезок. Также каждый узел знает, свое значение (фундаментальный элемент). Напишем рекурсивный метод, который принимает 6 параметров: границы запроса, границы левого и правого фундаментального отрезка, значение которое хранится в узле, индекс.

В методе rSum (r приставка для обозначения рекурсии) добавим в первой строке вывод всех 6 параметров. Границы запроса не меняются. Границы фундаментального отрезка уменьшаются в 2 раза на каждом вызове.

Если границы фундаментального отрезка внутри отрезка запроса - то просто возвращаем value. Это то значение, которое представляет из себя сумму всех детей. Это зеленый случай.

Строка 8 проверяет, что фундаментаьный отрезок и отрезок запроса не пересекаются. Это красный случай.

В противном случае это желтый случай и мы рекурсивно переходим к детям узла.

Вызвав данный метод мы получим следующие значения.

Попробуйте проследить за вызовами, чтобы понять как мы нашли сумму 21. Это был способ сверху вниз, начиная с корня и спускаясь вниз.

Другой способ - снизу вверх. Мы начинаем с самого последнего уровня, и пытаемся подняться наверх. Рассмотрим на конкретном примере.

Как только мы оказались на самом нижнем уровне, нам нужно скорее переходить на уровень выше, т.к. в этом и есть смысл дерева отрезков - использовать заранее высчитанные значения. Если мы будем оставаться на нижнем уровне, то будем складывать все узлы за линейное время. Разберемся с переходом на уровень выше.

У нас есть левая и правая границы. Рассмотрим для левой, для правой все будет также, но наоборот.

Каждый узел может быть четным или нечетным. Если узел четный (напомню, рассматриваем для левой границы), то это левый ребенок и правый (скорее всего) также будет входить в отрезок запроса. Если оба ребенка (скорее всего) входят в отрезок запроса, то мы можем сразу перейти к родителю, который уже знает их сумму. На изображении ниже это пример слева. Если запрос начинается с D, то мы переходим к родителю, т.е. к B.

Если узел нечетный, то он правый ребенок. Для левой границы это означает, что для суммы нужно учитывать только правый узел, а левый игнорировать. Нам нет смысла подниматься к родителю в таком случае, т.к. мы уже выяснили, что значение родителя нам не пригодится (родитель будет желтого типа). Но нам нужно перейти на уровень выше. К какому тогда элементу мы должны перейти? К следующему узлу родительского узла. На изображении выше это узел С.

Общая формула для подобных переходов - L = (L + 1) / 2. Если L четный - переходим к родителю. Если нет - к следующему элементу родителя.

Для правой границы работают теже правила, но зеркально отраженные.

В этом случае формула для новой границы справа будет R = (R - 1) / 2.

Если граница слева нечетная, это значит что это правый узел, он должен быть добавлен к общей сумме и только затем мы можем перейти к следующему узлу. Если узел четный, это означает что мы можем пока не прибавлять сумму т.к. мы можем сразу добавить родителя, который сразу добавит и левый и правый узел.

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

Метод нахождения суммы снизу вверх будет следующим

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

Другие функции

Распространенной практикой является выделение тех частей, которые могут измениться и тех частей, которые остаются постоянными. В нашем случае сама структура данных останется всегда одной, но функцию, которую мы вычисляем может меняться. Постарайтесь выделить те участки, которые могут измениться в отдельный объект, у которого будет метод вычисления значения функции и передавать этот объект в дерево отрезков как параметр конструктора (паттерн стратегия). В нашем случае это будут участки кода в методе set внутри метода while (не листовые узлы должны использовать абстрактную функцию, а не сумму) и в методах суммы (в варианте снизу вверх это прибавление значений при вычислении четного/нечетного элемента, при способе сверху вниз нужно заменить 0 на нейтральный элемент и выражение после return)

Откуда Log(N)

Если присмотреться, то можно заметить, что сложность вытекает из свойств бинарного дерева. Каждый раз, у нас может быть узел или желтого, или зеленого, или красного цвета. Но на каждом уровне желтых узлов не больше 2-х. Каждый раз, когда мы делим отрезок мы или сразу можем сказать сумму на этом подотрезке, или сразу выйти из рассчета зная что этот отрезок нам не нужен, или поделить отрезок на 2 в котором оба не могут быть желтыми.

В случае обновления нам нужно просто пройтись по высоте дерева, а высота дерева log(N).

Заключение

Дерево отрезков невероятно полезная структура дынных. Она позволяет находить значения любых ассоциативных функций за время O(log(N)), а также изменять значения за такое же время. Эта структура часто испопльзуется в олимпиадном программировани.