Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






Дерево отрезков - структура данных, которая позволяет реализовать с трудоемкостью O(log N) операции следующего типа:

Add(I, J, D) – изменение на величину D элементов массива в диапазоне индексов от I-го до J-го;

Update (I, J, V) – присвоение элементам массива в диапазоне индексов от I-го до J-го нового значения V;

Rsq(I, J) – нахождение суммы (Rmq – максимума) элементов массива в диапазоне индексов от I-го до J-го.

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

Распространенная аббревиатура Rsq расшифровывается как Range Sum Query, а Rmq как Range Maximum Query.

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

Рассмотрим сначала дерево отрезков для суммы. Пусть имеется массив A[1], A[2], …, A[N]. Построим бинарное дерево T следующим образом. Корень дерева будет храниться в элементе T[1] и содержать сумму элементов всего массива. Левый сын корня будет храниться в элементе T[2] и содержать сумму первой половины массива: A[1..N div2], а правый сын - в элементе T[3] и содержать сумму элементов A[N div 2+1..N]. В общем случае, если i-й элемент содержит сумму элементов с L-го по R-й, то его левым сыном будет элемент T[2*i] с суммой элементов A[L..(L+R) div 2], а правым – элемент T[2*i +1] с суммой A[(L+R) div 2+1..R]. Исключение, разумеется, составляют листья дерева - вершины, в которых L = R. Дерево состоит из 2N-1 вершин, строится с трудоемкостью O(N) и имеет высоту порядка O(log N).

Рассмотрим теперь операцию суммы на некотором отрезке индексов [L; R]. Мы встаем в корень дерева (i=1), и рекурсивно движемся вниз по этому дереву. Если в какой-то момент оказывается, что L и R совпадают с границами отрезка текущего элемента, то мы просто возвращаем значение текущего элемента T. Если же отрезок [L; R] целиком попадает в отрезок левого или правого сына текущего элемента, то мы рекурсивно вызываем себя из этого сына и найденное значение возвращаем. Наконец, если отрезок [L; R] частично принадлежит и отрезку левого сына, и отрезку правого сына, то делим его на два отрезка [L; M] и [M+1; R], где M = (L+R) div 2, и рекурсивно вызываем себя и для первого, и для второго отрезков, возвращая сумму найденных значений. В итоге вся операция суммирования работает за O (log N).

Теперь рассмотрим простейший вариант операции присвоения значения некоторому единственному элементу с индексомK. Будем спускаться по дереву от корня, ища тот лист, который содержит значение элемента A[K]. Когда мы найдём этот элемент, просто изменим соответствующее значение в массиве T и будем подниматься от текущего элемента обратно к корню, пересчитывая текущие значения T. Понятно, что таким образом мы изменим все значения в дереве, которые необходимо изменить. Общая трудоемкость составляет O(log N). Приведем реализацию описанных операций.

Procedure Build(i, L, R: longint);

{Построение дерева отрезков для суммы

i - номер вершины, L - нижняя граница в исходном массиве,

R - верхняя граница, первоначально 1 и N}

Var

m: longint;

Begin

if L=R then T[i]: =A[L]

else

begin

m: =(L+R) div 2;

Build(2*i, L, m);

Build(2*i+1, m+1, R);

T[i]: =T[2*i]+T[2*i+1];

end;

End;

Function Sum(L, R, i, Tl, Tr: longint): longint;

{L, R - интервал индексов в A для суммы - первоначально 1 и N,

Tl, Tr - границы поиска в массиве A, - первоначально 1 и N}

Var

m: longint;

Begin

if (L=Tl) and (R=Tr) then Sum: =T[i]

else

begin

m: =(Tl+Tr) div 2;

if R< =m then Sum: =Sum(L, R, 2*i, Tl, m)

else

if L> m then Sum: =Sum(L, R, 2*i+1, m+1, Tr)

else

Sum: =Sum(L, m, 2*i, Tl, m)+Sum(m+1, R, 2*i+1, m+1, Tr);

end;

End;

 

Procedure Update(Ind, NewVal, i, L, R: longint);

{одиночная модификация: в A[Ind] новое значение NewVal}

Var

m: longint;

Begin

if L=R then T[i]: =NewVal

else

begin

m: =(L+R) div 2;

if Ind< =m then Update(Ind, NewVal, 2*i, L, m)

else Update(Ind, NewVal, 2*i+1, m+1, R);

T[i]: =T[2*i]+T[2*i+1];

{пересчет значений при возврате из рекурсии}

end;

End;

 

Операция прибавления на отрезке реализуется сложнее одиночной модификации. Введем дополнительный массив Add размерности 2N – 1 и той же адресации, что и массив T. В i-м элементе будем хранить Add[i] - значение, которое нужно прибавить ко всем элементам этого отрезка. Если добавка распространяется не на все элементы, то это будет отражено в соответствующих вершинах поддерева с корнем I. Операция прибавления на отрезке [L; R] будет модифицировать эти значения, а операция суммирования на отрезке - просто добавлять к ответу все встретившиеся значения Add на пути от корня до вершин, которые представляют в совокупности отрезок [L; R].

Рекурсивная процедура Plus прибавления на отрезке имеет аргументы L, R, X, I, Tl, Tr. Здесь L и R описывают диапазон индексов исходного массива A, на котором к каждому элементу прибавляется значение X. Параметр Iопределяет индекс вершины в дереве T, содержащей диапазон индексов [Tl; Tr] исходного массива для поиска всех вершин дерева, которые описывают совместно отрезок [L; R]. Первоначально I = 1, что соответствует корню дерева. Значения Tl = 1 и Tr = N задают полный диапазон индексов исходного массива A. Значение X может быть как положительным, так и отрицательным. Порядок рекурсивных вызовов принципиально не меняется, что видно из текста процедуры Plus.

 

Procedure Plus(L, R, X, i, Tl, Tr: longint);

{в интервале индексов [L, R] к элементам A добавляется X}

Var

m: longint;

Begin

T[i]: =T[i]+X*(R-L+1);

if (L=Tl) and (R=Tr) then Add[i]: =Add[i]+X

else

begin

m: =(Tl+Tr) div 2;

if R< =m then Plus(L, R, X, 2*i, Tl, m)

else

if L> m then Plus(L, R, X, 2*i+1, m+1, Tr)

else

begin

Plus(L, m, X, 2*i, Tl, m);

Plus(m+1, R, X, 2*i+1, m+1, Tr);

end;

end;

End;

 

Рекурсивная функция суммирования имеет те же аргументы и строится по тому же принципу. Поскольку массив Addописывает изменение каждого элемента в диапазоне индексов [L; R], то общая добавка составляет сумму Add[i]*(R-L+1) по всем путям от корня дерева к вершинам, представляющим совместно весь диапазон [L; R].

 

Function Sum(L, R, i, Tl, Tr: longint): longint;

{L, R - интервал индексов для суммы,

Tl, Tr - границы поиска в дереве}

Var

m, h: longint;

Begin

if (L=Tl) and (R=Tr) then Sum: =T[i]

else

begin

m: =(Tl+Tr) div 2;

h: =Add[i]*(R-L+1);

if R< =m then Sum: =Sum(L, R, 2*i, Tl, m)+h

else

if L> m then Sum: =Sum(L, R, 2*i+1, m+1, Tr)+h

else

Sum: =Sum(L, m, 2*i, Tl, m)+Sum(m+1, R, 2*i+1, m+1, Tr)+h;

end;

End;

 

Трудоемкость обеих рассмотренных операций по-прежнему составляет O(log N).

Операция присвоения нового значения на диапазоне индексов реализуется с помощью дополнительного массива Val размерности 2N – 1 и той же адресации, что и массив T. Изначально массив Val заполняется некоторыми значениями, имеющими смысл ”неопределенность”. Если все элементы в текущем отрезке индексов массива T равны между собой, то соответствующий элемент массива Val примет это значение. При выполнении операции присвоения мы будем спускаться по дереву, как и ранее. Если в какой-то момент диапазон присваивания совпадет с границами текущего отрезка, то мы присвоим соответствующему элементу Val новое значение. При спуске необходимо отменять ранее определенные значения Val.

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

Приведем тексты программ для реализации описанных операций.

Procedure Update(L, R, NewVal, i, Tl, Tr: longint);

{в интервале индексов [L, R] в A[i] новое значение NewVal,

i-корень дерева отрезков}

Var

k, m: longint;

Begin

if (L=Tl) and (R=Tr) then

begin

Val[i]: =NewVal;

T[i]: =NewVal;

end

else

begin

k: =Val[i];

Val[i]: =-1;

if k< > -1 then

begin

Val[2*i]: =k; {спуск на уровень}

Val[2*i+1]: =k;

end;

m: =(Tl+Tr) div 2;

if R< =m then Update(L, R, NewVal, 2*i, Tl, m)

else

if L> m then Update(L, R, NewVal, 2*i+1, m+1, Tr)

else

begin

Update(L, m, NewVal, 2*i, Tl, m);

Update(m+1, R, NewVal, 2*i+1, m+1, Tr);

end;

T[i]: =T[2*i]+T[2*i+1];

{пересчет на обратном пути при выходе из рекурсии}

end;

End;

 

Function Sum(L, R, i, Tl, Tr: longint): longint;

{L, R - интервал индексов для суммы, i-корень дерева,

Tl, Tr - границы поиска в дереве}

Var

m: longint;

Begin

if (Val[i]< > -1) then Sum: =Val[i]*(R-L+1)

{все вершины дерева с корнем i имеют значение Val[i]}

else

if Tl=Tr then Sum: =T[i]

{дошли до листа без модификации значений}

else

begin

m: =(Tl+Tr) div 2;

if R< =m then Sum: =Sum(L, R, 2*i, Tl, m)

else

if L> m then Sum: =Sum(L, R, 2*i+1, m+1, Tr)

else

Sum: =Sum(L, m, 2*i, Tl, m)+Sum(m+1, R, 2*i+1, m+1, Tr);

end;

End;

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

Прямоугольники. На координатной плоскости задано N прямоугольников со сторонами, параллельными координатным осям. Найти площадь фигуры, получающейся в результате объединения прямоугольников.

Ввод из файла INPUT.TXT. В первой строке содержится значение N (1 ≤ N ≤ 100000). В каждой из следующих N строк – четыре целых числа Ai, Bi, Ci, Di через пробел, определяющие координаты левого верхнего и правого нижнего углов очередного прямоугольника (-109 ≤ Ai, Bi, Ci, Di ≤ 109).

Вывод в файл OUTPUT.TXT действительного числа с точностью до двух знаков после запятой – площади фигуры.

Пример

Ввод

5 15 25 5

0 10 20 0

Вывод

В [4] описано решение этой задачи для меньшей размерности. Нужно отсортировать координаты углов прямоугольников по возрастанию и использовать метод заметания. Будем продвигать вертикальную прямую слева направо, отмечая изменение длины сечения нашей фигуры по оси Y. При встрече точки, соответствующей левой стороне прямоугольника, длина сечения может увеличиться, а при встрече правой стороны прямоугольника уменьшиться. Очередная прибавка к площади составит произведение длины отрезка по оси X на длину сечения.

Длина сечения находится также методом заметания. Создадим еще один массив координат вершин прямоугольников, но уже в порядке возрастания координаты Y. Изменение длины сечения связано с добавлением или удалением отрезка по оси Y. Будем просматривать точки вершин уже в порядке возрастания по оси Y, поддерживая счетчик числа вложенных отрезков. При встрече левого конца отрезка к счетчику прибавляется единица, а на правом конце отрезка она вычитается. Если при некотором значении координаты Y счетчик оказался больше нуля, а при другом значении снова обратился в ноль, то разность значений должна добавиться в длину сечения.

Оценим трудоемкость этого метода. Быстрая сортировка координат по каждой оси имеет трудоемкость O(N log N). Для каждой новой точки по оси X потребуется перебрать точки сечения по оси Y. Общая трудоемкость метода составит O(N2). При заданной размерности описанный подход не годится.

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

Обозначим через Ymin и Ymax минимальное и максимальное значения координаты Y. Отрезок [Ymin; Ymax] окажется разделенным на N-1 отрезков S1, S2, …, SN-1. Каждая вертикальная сторона прямоугольника покрывает один или несколько таких отрезков.

Снова используем метод заметания, продвигая сканирующую прямую по оси X. Для каждого отрезка Si будем отмечать в счетчике Ai, сколько раз отрезок Si входит в сечение. Добавление и удаление стороны прямоугольника по оси Y, покрывающей отрезки Sk, Sk+1, …, Sm, вызовет увеличение или уменьшение на единицу счетчиков Ak, Ak+1, …, Am.

Организуем по массиву A1, A2, …, AN-1 дерево отрезков для минимума. Введем еще один дополнительный массив Lm размерности 2N – 1 и той же адресации, что и массив T. В i-м элементе будем хранить Lm[i] – суммарную длину отрезков в дереве с корнем i, на которых достигается минимум. Значения массива Lm модифицируются при изменении дерева. Если в корне всего дерева минимум равен нулю, то значение Lm[1] определяет суммарную длину отрезков Si, не входящих в сечение по оси Y. Тогда длину сечения составит величина Ymax - Ymin - Lm[1].

Поскольку каждое изменение элементов массива Ak, Ak+1, …, Am имеет трудоемкость O(log N), общая трудоемкость алгоритма оценивается величиной O(N log N). Ниже приводится полный текст программы.

 

Program Rectang;

Const

MM=420;

{максимальное количество прямоугольников -

почти предел для Turbo Pascal, в Delphi возможно и 200000}

Var

i, k, N, M: longint;

S: double; {площадь объединения прямоугольников}

X1, Y1: array[1..2*MM] of longint;

{X1, Y1 - координаты верхних левых и нижних правых углов,

отсортированных по X}

Ind: array [1..2*MM] of longint;

{Ind[i]-индекс в (X1, Y1) диагональной вершины прямоугольника}

X2, Y2: array[1..2*MM] of longint;

{координаты (X1, Y1), отсортированные по Y}

Ref1: array [1..2*MM] of longint;

{Ref1[i]-индекс в массиве (X2, Y2) элемента (X1[i], Y1[i])}

Ref2: array [1..2*MM] of longint;

{Ref2[i]-индекс в массиве (X1, Y1) элемента (X2[i], Y2[i])}

{Ref1, Ref2 для быстрой связи массивов (X1, Y1) и (X2, Y2)}

Q: array [1..8*MM] of longint; {дерево минимумов для A[i]}

Add: array [1..8*MM] of longint;

{Add[i] - модифицирующая добавка ко всем сыновьям вершины i}

Lm: array [1..8*MM] of longint;

{суммарные длины отрезков, где в дереве достигается MIN}

Ch: char;

c, d, L, R, V, W, XPred: longint;

Lx, Ly, Lmax: longint;

Fin, Fout: text;

 

Function Min(a, b: longint): longint;

Begin

if a< b then Min: =a

else Min: =b

End;

 

Function Max(a, b: longint): longint;

Begin

if a> b then Max: =a

else Max: =b

End;

 

Procedure Sort1(L, R: longint); {быстрая сортировка по X}

Var

i, j, k, x, y, w, a, b: longint;

Begin

i: =L; { нижний индекс }

j: =R; { верхний индекс }

k: =(L+R) div 2;

x: =X1[k]; y: =Y1[k];

Repeat

While (X1[i]< x) or

((X1[i]=x) and (Y1[i]< y)) do i: =i+1;

{для одного значения X выбор по возрастанию Y позволяет

рассмотреть закрывающую сторону прямоугольника раньше}

While (X1[j]> x) or

((X1[j]=x) and (Y1[j]> y)) do j: =j-1;

if i< =j then

begin

w: =X1[i]; X1[i]: =X1[j]; X1[j]: =w;

w: =Y1[i]; Y1[i]: =Y1[j]; Y1[j]: =w;

a: =Ind[i]; b: =Ind[j];

if (a< > j) or (b< > i) then {меняются местами не противоположные углы прямоугольника}

begin

Ind[i]: =b; Ind[j]: =a;

Ind[a]: =j; Ind[b]: =i;

end;

i: =i+1; j: =j-1

end

Until i> j;

if L< j then Sort1(L, j);

if i< R then Sort1(i, R);

End;

 

Procedure Sort2(L, R: longint); {быстрая сортировка по Y}

Var

i, j, y, w, a, b: longint;

Begin

i: =L; { нижний индекс }

j: =R; { верхний индекс }

y: =Y2[(L+R) div 2];

Repeat

While Y2[i]< y do i: =i+1;

While Y2[j]> y do j: =j-1;

if i< =j then

begin

w: =Y2[i]; Y2[i]: =Y2[j]; Y2[j]: =w;

w: =X2[i]; X2[i]: =X2[j]; X2[j]: =w;

a: =Ref2[i]; b: =Ref2[j];

w: =Ref2[i]; Ref2[i]: =Ref2[j]; Ref2[j]: =w;

Ref1[a]: =j; Ref1[b]: =i;

i: =i+1; j: =j-1

end

Until i> j;

if L< j then Sort2(L, j);

if i< R then Sort2(i, R);

End;

 

Procedure Build(i, L, R: longint);

{построение дерева минимумов по нулевому массиву}

{i - номер вершины, L - нижняя граница, R - верхняя граница

Lm[i]-сумма длин интервалов с MIN значением для i-й вершины}

Var

m: longint;

Begin

if L=R then Lm[i]: =Y2[L+1]-Y2[L]

else

begin

m: =(L+R) div 2;

Build(2*i, L, m);

Build(2*i+1, m+1, R);

Lm[i]: =0;

if Q[i]=Q[2*i] then {модифицирующих добавок сначала нет}

Lm[i]: =Lm[i]+Lm[2*i];

if Q[i]=Q[2*i+1] then

Lm[i]: =Lm[i]+Lm[2*i+1];

end;

End;

 

Function Minim(L, R, i, Tl, Tr: longint): longint;

{поиск минимума элементов массива по интервалу индексов}

{L, R - интервал индексов для минимума,

i – индекс корня для поиска в дереве, Tl, Tr - границы поиска}

Var

m: longint;

Begin

if (L=Tl) and (R=Tr) then Minim: =Q[i]

else

begin

m: =(Tl+Tr) div 2;

if R< =m then Minim: =Minim(L, R, 2*i, Tl, m)+Add[i]

else

if L> m then Minim: =Minim(L, R, 2*i+1, m+1, Tr)+Add[i]

else

Minim: =Min(Minim(L, m, 2*i, Tl, m), Minim(m+1, R, 2*i+1, m+1, Tr))+

Add[i];

end;

End;

 

Function Long(L, R, i, Tl, Tr: longint): longint;

{сумма нулевых отрезков, (L, R) - интервал индексов для поиска,

i – индекс корня для поиска в дереве, (Tl, Tr) - границы поиска}

Var

m: longint;

Begin

if (L=Tl) and (R=Tr) then

if Q[i]=0 then Long: =Lm[i] {если MIN=0}

else Long: =0

else

begin

m: =(Tl+Tr) div 2;

if R< =m then Long: =Long(L, R, 2*i, Tl, m)

else

if L> m then Long: =Long(L, R, 2*i+1, m+1, Tr)

else

Long: =Long(L, m, 2*i, Tl, m)+Long(m+1, R, 2*i+1, m+1, Tr);

end;

End;

 

Procedure Plus(L, R, X, i, Tl, Tr: longint);

{на отрезке (Y2[L], Y2[R]) добавление значения X в A[i] для Min,

модификация массива Lm - суммы длин отрезков с Min}

Var

m: longint;

Begin

if (L=Tl) and (R=Tr) then

begin

Q[i]: =Q[i]+X;

Add[i]: =Add[i]+X;

end

else

begin

m: =(Tl+Tr) div 2;

if R< =m then Plus(L, R, X, 2*i, Tl, m)

else

if L> m then Plus(L, R, X, 2*i+1, m+1, Tr)

else

begin

Plus(L, m, X, 2*i, Tl, m);

Plus(m+1, R, X, 2*i+1, m+1, Tr);

end;

Q[i]: =Min(Q[2*i], Q[2*i+1])+Add[i];

{Add[i]-добавка для каждого элемента в интервале

индексов вершины i, т.е. для всех потомков i}

Lm[i]: =0;

if Q[i]=Q[2*i]+Add[i] then

Lm[i]: =Lm[i]+Lm[2*i];

if Q[i]=Q[2*i+1]+Add[i] then

Lm[i]: =Lm[i]+Lm[2*i+1];

end;

End;

 

Begin

Assign(Fin, 'input.txt');

Reset(Fin);

ReadLn(Fin, M);

N: =2*M; {количество вершин прямоугольников}

For i: =1 to M do

begin

k: =2*(i-1)+1;

ReadLn(Fin, X1[k], Y1[k], X1[k+1], Y1[k+1]);

Ind[k]: =k+1; {связь противоположных вершин прямоугольников}

Ind[k+1]: =k;

end;

Close(Fin);

Sort1(1, N); {сортировка точек (X1, Y1) по координате X}

For k: =1 to N do

begin

X2[k]: =X1[k];

Y2[k]: =Y1[k];

Ref1[k]: =k; {Ref1[i]-индекс (X1[i], Y1[i]) в массиве (X2, Y2)}

Ref2[k]: =k; {Ref2[i]-индекс (X2[i], Y2[i]) в массиве (X1, Y1)}

end;

Sort2(1, N); {сортировка точек (X2, Y2) по координате Y}

For i: =1 to 4*N do {инициализация дерева минимумов}

begin

Q[i]: =0;

Add[i]: =0;

Lm[i]: =0;

end;

Build(1, 1, N-1); {построение массива Lm для нулевого дерева MIN}

XPred: =X1[1]; {предыдущая координата по х}

Ly: =0; {здесь будет длина сечения по y}

Lmax: =Y2[N]-Y2[1]; {диапазон значений по оси Y}

S: =0; {общая площадь объединения прямоугольников}

For i: =1 to N do

begin

Lx: =X1[i]-XPred; {длина очередного прямоугольника по x}

XPred: =X1[i];

V: =Y1[i]; {координаты концов нового отрезка}

W: =Y1[Ind[i]];

c: =Ref1[i];

d: =Ref1[Ind[i]]; {индексы нижней и верхней точек в (X2, Y2)}

L: =Min(c, d);

R: =Max(c, d);

if V> W then {X[i] - левая сторона прямоугольника}

Plus(L, R-1, 1, 1, 1, N-1) {добавили отрезок}

else {X[i] - правая сторона прямоугольника}

Plus(L, R-1, -1, 1, 1, N-1); {убрали отрезок}

{если углы прямоугольников задаются в другом порядке: левый

нижний, а затем правый верхний, то изменение на if V< W}

S: =S+Lx*Ly; {учли пройденную площадь}

Ly: =Lmax-Long(1, N-1, 1, 1, N-1);

{вычли сумму длин нулевых отрезков, Ly-длина сечения по y}

end;

Assign(Fout, 'output.txt');

Rewrite(Fout);

WriteLn(Fout, S: 0: 2);

{2 знака после запятой без ведущих пробелов}

Close(Fout);

End.

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.054 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал