8. Дерево отрезков
Дерево отрезков (segment tree) — структура данных, которая позволяет эффективно выполнять операции с отрезками массива. Это полное бинарное дерево, в котором каждая вершина отвечает за некоторый отрезок в массиве: Корень — за весь массив. У каждой вершины, отвечающей за отрезок длиной больше 1, есть две дочерние вершины — за левую и правую половины этого отрезка. Листья — за отдельные элементы (отрезки длиной 1). Хранимое в узле значение зависит от задачи или запроса, который необходимо обрабатывать. Принцип построения Дерево строится рекурсивно: Если вершина — лист, в качестве значения берут значение соответствующей ячейки. Если вершина — отрезок, его делят на два и в качестве значения берут сумму детей. Свойства: Высота дерева — порядка log n: на каждом новом уровне длина отрезка уменьшается вдвое. Для массива из n элементов дерево отрезков имеет около 2n вершин. При n, отличных от степеней двойки, не все уровни дерева будут полностью заполнены. Операции С помощью дерева отрезков можно выполнять, например: Нахождение суммы, минимума, максимума элементов массива в заданном отрезке. Изменение элементов массива: как изменение значения одного элемента, так и изменение элементов на целом подотрезке (например, присвоение всем элементам какого-либо значения). Объединение нескольких операций в одной задаче, например, присвоение и добавление на отрезке и поиск максимума. Сложность После построения дерева отрезков многие операции можно делать эффективно — за O(log N), где N — это размер исходного массива. Например: Запрос суммы — каждый запрос на отрезке разбивают на 2 log N отрезков и находят сумму на каждом из них за O(1), используя предпросчитанные значения. Запрос модификации — от изменения одного элемента значение суммы изменится в одной вершине на каждом уровне дерева отрезков (в которую входит этот элемент). Значения суммы пересчитывают рекурсивно только в этих вершинах. Реализация Дерево отрезков реализуется на обычном массиве. Функционально оно занимает 2n вершин, но в некоторых случаях 2n индексов может не хватить, например, когда размер изначального массива нечётный. Чтобы оптимально использовать память, можно использовать 4n. Особенность: дерево отрезков потребляет линейный объём памяти: стандартному дереву отрезков требуется порядка 4n элементов памяти для работы над массивом размера n
Дерево отрезков (segment tree) — структура данных, которая позволяет эффективно выполнять операции с отрезками массива. Это полное бинарное дерево, в котором каждая вершина отвечает за некоторый отрезок в массиве: Корень — за весь массив. У каждой вершины, отвечающей за отрезок длиной больше 1, есть две дочерние вершины — за левую и правую половины этого отрезка. Листья — за отдельные элементы (отрезки длиной 1). Хранимое в узле значение зависит от задачи или запроса, который необходимо обрабатывать. Принцип построения Дерево строится рекурсивно: Если вершина — лист, в качестве значения берут значение соответствующей ячейки. Если вершина — отрезок, его делят на два и в качестве значения берут сумму детей. Свойства: Высота дерева — порядка log n: на каждом новом уровне длина отрезка уменьшается вдвое. Для массива из n элементов дерево отрезков имеет около 2n вершин. При n, отличных от степеней двойки, не все уровни дерева будут полностью заполнены. Операции С помощью дерева отрезков можно выполнять, например: Нахождение суммы, минимума, максимума элементов массива в заданном отрезке. Изменение элементов массива: как изменение значения одного элемента, так и изменение элементов на целом подотрезке (например, присвоение всем элементам какого-либо значения). Объединение нескольких операций в одной задаче, например, присвоение и добавление на отрезке и поиск максимума. Сложность После построения дерева отрезков многие операции можно делать эффективно — за O(log N), где N — это размер исходного массива. Например: Запрос суммы — каждый запрос на отрезке разбивают на 2 log N отрезков и находят сумму на каждом из них за O(1), используя предпросчитанные значения. Запрос модификации — от изменения одного элемента значение суммы изменится в одной вершине на каждом уровне дерева отрезков (в которую входит этот элемент). Значения суммы пересчитывают рекурсивно только в этих вершинах. Реализация Дерево отрезков реализуется на обычном массиве. Функционально оно занимает 2n вершин, но в некоторых случаях 2n индексов может не хватить, например, когда размер изначального массива нечётный. Чтобы оптимально использовать память, можно использовать 4n. Особенность: дерево отрезков потребляет линейный объём памяти: стандартному дереву отрезков требуется порядка 4n элементов памяти для работы над массивом размера n