Задача RMQ – 2. Дерево отрезков

    В первой части нашей темы мы рассмотрели решение задачи static RMQ за (O(nlogn), O(1)). Теперь мы разберёмся со структурой данных, называемой дерево отрезков, или интервалов (в англоязычной литературе – segment tree или interval tree). С помощью неё можно решать dynamic RMQ за (O(n), O(logn)).

    Определение



    Введём понятие дерева отрезков. Для удобства дополним длину массива до степени двойки. В добавленные элементы массива допишем бесконечности (за бесконечностью стоит понимать, например, число, больше которого в данных ничего не появится). Итак, дерево отрезков это двоичное дерево, в каждой вершине которого написано значение заданной функции на некотором отрезке. Функция в нашем случае – это минимум.

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



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



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

    Хранить дерево будем подобно двоичной куче. Заведём массив T[2n – 1]. Корень будет лежать в первом элементе массива, а сыновья i-ой вершины будут лежать в элементах с номерами 2i и 2i + 1 – левый и правый соответственно. Сразу можно заметить очевидное свойство: T[i] = min(T[2i], T[2i + 1]) для i-ой вершины, не являющейся листом. Листы, к слову, будут лежать при такой нумерации в элементах с номерами от n до 2n – 1.

    Построение



    Построим дерево, пробежавшись по элементам с (n – 1)-ого по первый, считая минимум значений в сыновьях для каждой вершины.
    Начиная с этой статьи я буду давать код для большей наглядности.

    const int INF = INT_MAX;
    
    void build_tree(const vector<int>& V)
    {
    	// размер, доведённый до степени двойки
    	int n = (1 << (log(n - 1) + 1));
    	V.resize(2 * n, INF);	
    
    	// инициализируем листы
    	for (int i = n; i < 2 * n; i++)
    		V[i] = V[i - n];
    
    	// и все остальные вершины
    	for (int i = n - 1; i > 0; i--)
    		V[i] = min(V[2 * i], V[2 * i + 1]);
    }
    


    Функция build_tree(V) превращает массив V в дерево отрезков для этого массива. Итак, как теперь по отрезку найти минимум на нём? Для этого введём понятие фундаментального отрезка.

    Запрос минимума



    Назовём фундаментальным отрезком в массиве такой отрезок, что существует вершина в дереве, которой он соответствует. Разобьём наш отрезк на минимальное количество непересекающихся фундаментальных. Покажем, что на каждом уровне их количество не превосходит 2.



    Возьмём самый большой фундаментальный отрезок в разбиении. Пусть его длина – 2t. Заметим, что фундаментальных отрезков длиной 2t – не более двух (1). Возьмём самый левый из имеющихся максимальных фундаментальных. Будем двигаться от него налево. Заметим, опять же, что длины отрезков будут убывать (2). Так же и с правым из максимальных. Тем самым получим, что фундаментальных отрезков – не более 2t, что не превосходит 2logn. Пункты (1) и (2) в доказательстве я оставлю для самостоятельного осмысления.

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

    Заведём два указателя – l и r, с помощью которых будем находить очередные фундаментальные отрезки разбиения. Изначально установим l и r указывающими на листы, соответствующие концам отрезка запроса. Заметим, что если l указывает на вершину, являющуюся правым сыном своего родителя, то эта вершина принадлежит разбиению на фундаментальные отрезки, в противном случае не принадлежит. Аналогично с указателем r – если он указывает на вершину, являющуюся левым сыном своего родителя, то добавляем её в разбиение. После этого сдвигаем оба указателя на уровень выше и повторяем операцию. Продолжаем операции пока указатели не зайдут один за другой.

    Находя очередной фундаментальный отрезок, мы сравниваем минимум на нём с текущим найденным минимумом и уменьшаем его в случае необходимости. Асимптотика работы алгоритма – O(logn), т. к. на каждом уровне мы выполняем константное число операций, а всего уровней – logn.

    int rmq_up(vector<int>& T, int l, int r)
    {
    	int ans = INF;
    	int n = T.size() / 2;
    	l += n - 1, r += n - 1;
    	while (l <= r)
    	{
    		// если l - правый сын своего родителя, 
    		// учитываем его фундаментальный отрезок
    		if (l & 1)
    			ans = min(ans, T[l]);
    		// если r - левый сын своего родителя, 
    		// учитываем его фундаментальный отрезок
    		if (!(r & 1))
    			ans = min(ans, T[r]);
    		// сдвигаем указатели на уровень выше
    		l = (l + 1) / 2, r = (r - 1) / 2;
    	}		
    	return ans;
    }
    


    Модификация



    Теперь научимся изменять значение элемента дерева. Заметим, что для каждого листа есть ровно logn фундаментальных отрезков, которые его содержат – все они соответствуют вершинам, лежащим на пути от нашего листа до корня.



    Значит, при изменении элемента достаточно просто пробежаться от его листа до корня и обновить значение во всех вершинах на пути по формуле T[i] = min(T[2i], T[2i + 1]).

    void update(vector<int>& T, int i, int x)
    {
    	int n = T.size() / 2;
    	i += n – 1;
    	T[i] = x;
    	while (i /= 2)
    		T[i] = min(T[2 * i], T[2 * i + 1]);
    }
    


    Ура! Получаем решение задачи Dynamic RMQ за (O(n), O(logn)).

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

    Поделиться публикацией
    Похожие публикации
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 16
    • 0
      У дерева отрезков тьма-тьмущая применений окромя минимума ведь, это же моноидальная структура.
      • 0
        Конечно, некоторый шмат разных применений я дальше опишу.
      • 0
        А в чем вы так красиво деревья рисуете? Есть какой-то специальный софт?
        • +1
          О да, специальная софтина это просто-напросто автофигуры в ворде :)
          Пост я готовил в нём, и возможностей мне вполне хватило.
          • +1
            Я обычно юзаю graphViz
            • 0
              В Google Docs есть тип документа Drawing, в нём тоже получаются отличные рисунки
            • –3
              Интересно, один я вздрагиваю уже в 4-й раз за сегодня, натыкаясь на школьную задачку? Такой флешбек…

              Вообще, за 12 лет практики ни разу не пригодились те олимпиадные задачки и алгоритмы, которыми нас так мучали на информатике. Кому-то пригодились? Поделитесь!

              • 0
                Проблема в том, что они были написаны во всех стандартных библиотеках давным-давно. Программист просто превращается в архитектора, слепляющего блоки написанных алгоритмов в единое целое.

                Это надо сказать, у вас хорошая информатика была, если вы двенадцать лет назад на ней деревьями отрезков занимались в виде школьных задачек.
                • 0
                  Вроде бы, деревья отрезков совсем не были распространены двенадцать лет назад :)

                  На самом деле, это пригождается, если нужно написать какой-нибудь кусок кода, который должен обрабатывать огромные данные очень быстро.
                  • 0
                    Регулярно. Работая со встраиваемыми системами, или с системами, главное конкурентное преимущество которых — производительность, приходится выжимать из железяк тот максимум, на который они способны. Стандартные реализации в подобных условиях могут отсутствовать, либо быть недостаточно хорошими.
                  • 0
                    Хорошая статья, спасибо. К слову, описание интервальных деревьев есть в Кормене.

                    Для Haskell существует чистая функциональная реализация (возможно, кому-то будет интересно на неё посмотреть — особенно в контексте взвешенных моноидов):

                    hackage.haskell.org/packages/archive/SegmentTree/0.2/doc/html/Data-SegmentTree.html

                    Приходилось использовать в проекте, был зело доволен.
                    • 0
                      В следующей статье мы научимся делать запрос сверху.
                      Обещанного три года ждут?

                      Два уже почти прошли :-)
                      • 0
                        Возможно ли реализовать универсальное дерево отрезков, которое поддерживает модификацию на интервале и запрос на интервале? В чем главная идея?
                        Под универсальным, подразумевается реализация в виде шаблона, у которого функция «комбинирования значений» (F1) и функция «комбинирования модификаций» (F2) являются параметрами шаблона.
                        Например:
                        1) <запрос минимума, присвоение на отрезке>: F1 = min, F2 = assign
                        2) <запрос XOR-a, прибавление на отрезка>: F1 = XOR, F2 = add
                        Сам пробовал это сделать через ленивую модификацию, добавив третий параметр шаблона «функция комбинирования значения и модификации» — не получилось, работало за квадрат при некотором наборе данных.
                        В общеизвестном пособии для начинающих есть только частные примеры.
                        • 0
                          Надо уточнить, что в коде под log подразумевается двоичный логарифм, а то Си-подобный синтаксис немного сбивает с толку.
                          С библиотекой math.h такой логарифм реализуется: log10(x) / log(2).
                          • 0
                            Пардон: log(x) / log(2) или же log10(x) / log10(2).
                            • 0
                              В math.h есть стандартная функция log2, так что нет смысла изобретать велосипед.

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