Pull to refresh

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

Algorithms *
В первой части нашей темы мы рассмотрели решение задачи 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)).

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

Tags:
Hubs:
Total votes 28: ↑27 and ↓1 +26
Views 46K
Comments Comments 16