Дерево отрезков - структура данных, которая позволяет реализовать с трудоемкостью 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 div 2], а правый сын - в элементе 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;