Сегментни Дървета

Segment Trees

В тази тема ще разгледаме Сегментни Дървета - една много мощна структура данни, която понякога се ползва вместо индексни дървета, а също и като имплементация на динамично RMQ. Сегментните дървета могат относително лесно да бъдат надградени и до структура, която поддържат както питане, така и ъпдейт на интервал.
Автор: Александър Георгиев

В темата за индексни дървета видяхме една възможна имплементация на структура данни, която позволява бърз ъпдейт на елемент и питане за интервал. Тук ще разгледаме друга структура, позволяваща същите операции със същите сложности, наричана сегментно дърво. Макар и сходни откъм сложност на операциите, сегментните дървета са малко по-бавни и изискват малко повече памет от индексните такива.

За разлика от индексните дървета, обаче, със съвсем малка промяна, сегментните позволяват търсене на min() и max(), които ще разгледаме в темата минимум в интервал. Малко по-сложна тяхна версия пък дава възможност за питане и ъпдейт на интервал, което ще разгледаме в темата за интервални дървета.

Поддържани операции и сложности

Поддържаните операции, които ще разгледаме в тази тема, са същите като и при индексните дървета - бързо търсене и променяне на елемент за операции като сума, произведение, XOR, и други комутативни функции. Както и в темата за индексни дървета, тук ще разгледаме варианта със сума, като тези за останалите функции се правят по аналогичен начин.

Строене

Строенето на сегментно дърво от N елемента става със сложност O(N).

Добавяне, Триене, Променяне

И трите операции се правят с една и съща функция, която е със сложност O(log(N)).

Търсене

Търсенето в сегментно дърво е със сложност O(log(N)).

Идеално балансирано дърво

Представянето на сегментно дърво е чрез идеално балансирано двоично дърво. Това е дърво, всяко ниво на което е изцяло запълнено, потенциално с изключение на последното.

Идеално балансираните двоични дървета са много удобни за имплементиране, тъй като лесно могат да бъдат пазени в масив, не се нуждаят от указатели към децата и бащата на върховете, и се възползват от cache locality (тоест са относително бързи).

?Можем да означим двете деца на връх node с node * 2 + 0 и node * 2 + 1. Макар и да няма смисъл да добавяме нула, както ще видите по-долу кодът става симетричен и намали шанса да направите грешка в индексите.
Как можем да пазим такова дърво в масив? За удобство ще жертваме един елемент от масива (този с индекс 0) и коренът на дървото ще е елементът с индекс 1. Децата на корена ще са с индекси 2 и 3. Децата на 2 ще са 4 и 5, а на 3 ще са 6 и 7. По-общо, децата на връх node са node * 2 и node * 2 + 1, а бащата на връх node е node / 2.

Ето пример за идеално балансирано двоично дърво, държащо във върховете си индексите на масива, които ще ползваме за всеки връх:

Ако помните, по-рано ползвахме същия вид дърво (и представяне в масив) за имплементацията на структурата данни приоритетна опашка чрез пирамида.

Идея

Както и при префиксните масиви и индексните дървета и тук не можем да "добавяме" и "изтриваме" елемент между два други. Отново ще пазим фиктивни позиции за тях, като ги инициализираме с някаква стойност, която не влияе на търсенето. Например, бихме ползвали нула за функции като сума и xor, или едно за умножение. За да "добавим" елемент, всъщност ще променим стойността му от дефолтната на новата. За да "изтрием" елемент ще върнем неговата стойност до дефолтната му. Тоест ни интересува единствено операцията "променяне на елемент", като с нея можем да симулираме добавяне и премахване.

Нека искаме да пазим до N елемента. Сегментното ни дърво ще бъде идеално балансирано дърво с около? 2 * N върха.
?Реално броят елементи в дървото е между 2N и 3N в по-икономичния вариант, и потенциално до 4N ако искаме да направим дървото пълно.
На най-долното ниво на дървото ще пазим стойностите на N-те елемента, а всеки друг връх ще държи сумата на децата си. Така върховете в пред-последното ниво - около N/2 на брой - ще държат сумите на всички непресичащи се двойки съседни елементи. Върховете в по-горното ниво пък ще държат сумите на четворки съседни елементи и т.н. На най-високото ниво, коренът на дървото ще държи сумата на всички елементи.

Нека, например, имаме масив с 13 елемента със стойности (42, 13, 17, 1, -18, 3, -2, 9, 22, 4, 19, -23, 12). Сегментното дърво, пазещо информацията за този масив, би изглеждало по следния начин:

В паметта това дърво би било масив с 27 елемента:
(неизползван, 99, 65, 34, 73, -8, 22, 12, 55, 18, -15, 7, 26, -4, 12, 0, 42, 13, 17, 1, -18, 3, -2, 9, 22, 4, 19, -23, 12)

Доста удобно е да дефинираме размера на масива, в който ще държим перфектно балансираното дърво, като число, което е точна степен на двойката. Така много лесно можем да намерим индекса на произволно листо idx:
const
int
TREE_SIZE
=
32
;
int
tree[TREE_SIZE]
;
int
getLeaf(
int
idx) {
return
idx
+
TREE_SIZE
/
2
;
}
А каква степен на двойката да ползваме? Намираме най-малкото число, степен на двойката, което е по-голямо или равно на N, и после го умножаваме по две. Например, ако имаме 5 елемента ще ни трябва масив с 16 позиции (8 е най-малката степен на две, по-голяма или равна на 5, и ни трябват още толкова за върховете от дървото над листата).

Промяна на елемент

За да променим стойността на даден елемент, първо намираме разликата между новата му стойност и досегашната му такава.
?Дървото е така конструирано, че можем лесно да намерим текущата стойност на k-тия елемент - тя се пази в k-тото листо на дървото.
Нека означим тази разлика с delta (забележете, че delta спокойно може да е отрицателно). Започвайки от листото, отговарящо за елемента, който променяме, тръгваме нагоре по дървото и добавяме delta към всеки връх, който срещнем. Продължаваме това докато стигнем до корена. Тъй като дървото е идеално балансирано, неговата дълбочина е точно log(N), и съответно сложността на тази операция е O(log(N)).

Примерен код, който имплементира това:
void
update(
int
idx
,
int
delta) { idx
=
getLeaf(idx)
;
while
(idx) { tree[idx]
+
=
delta
;
idx
/
=
2
;
} }

Нека разгледаме как би се променило дървото, ако променим елемента с индекс пет от 3 на 16. Стойността delta е 16 – 3 = 13. Ъпдейтвайки дървото нагоре, се получава следното:

Ако забелязвате, след като обновим всички върхове по пътя до корена нагоре по дървото, структурата отново има вида, който искахме: върховете в най-долното ниво пазят текущите стойности на масива, а всеки връх от по-горните нива пази сумата на децата си.

Търсене

Как можем да питаме за сумата на числата в интервал [left, right] от дадения масив? Нека idxL и idxR сочат листата, съдържащи информация за, съответно, елементите с индекс left и right.

Ако left и right (и, съответно, idxL и idxR) съвпадат, то питаме за едно единствено число, и можем просто да върнем стойността на листото, отговарящо за този индекс (tree[idxL]).

В противен случай трябва да обходим част от дървото. Първо, сумираме числата в idxL и idxR. Към тях трябва да добавим сумата на всички елементи, намиращи се стриктно между тях. За целта се качваме едно ниво нагоре в дървото (idxL /= 2, idxR /= 2;), и:
  • Ако idxL и idxR съвпадат, това значи, че сме обработили всички елементи между началните два индекса, следователно приключваме работа и връщаме намерената сума.
  • Ако сме дошли в idxL от лявото му дете, то трябва да добавим към сумата дясното му такова (idxL * 2 + 1).
  • Ако сме дошли в idxR от дясното му дете, то трябва да добавим към сумата лявото му такова (idxR * 2 + 0).
Продължаваме нагоре по нивата със същата процедура докато двата индекса се срещнат.

Това като код изглежда по следния начин (считаме, че знаем, че имаме 13 елемента, тоест дървото ни ще е с 32 върха):
int
query(
int
left
,
int
right) {
int
idxL
=
getLeaf(left)
;
int
idxR
=
getLeaf(right)
;
if
(idxL
=
=
idxR)
return
tree[idxL]
;
int
sum
=
tree[idxL]
+
tree[idxR]
;
bool
isL
=
!
(idxL
%
2
)
;
idxL
/
=
2
;
bool
isR
=
(idxR
%
2
)
;
idxR
/
=
2
;
while
(idxL
!
=
idxR) {
if
(isL) sum
+
=
tree[idxL
*
2
+
1
]
;
if
(isR) sum
+
=
tree[idxR
*
2
+
0
]
;
isL
=
!
(idxL
%
2
)
,
idxL
/
=
2
;
isR
=
(idxR
%
2
)
,
idxR
/
=
2
;
}
return
sum
;
}

Вижте следния пример за сумиране на числата в интервала [1, 11] (от 13 до -23):
!Цялата идея на сегментните дървета е да се сумират възможно по-големи поддървета, които изцяло попадат в интервала (left, right). Пример за такива поддървета са тези, започващи от върховете със стойности 18, -8, 26, и 19.
Червените върхове са тези, от които започваме. Черните са тези, през които минават idxL и idxR. Сините са тези, които добавяме към първоначалната сума, в следствие на това, че сме се качили от ляво дете в левия клон или от дясно дете в десния клон. Можем да се убедим, че сумата 13 + 18 + (-8) + 26 + 19 + (-23) = 45 наистина е равна на сумата на числата в интервала (13 + 17 + 1 + (-18) + 3 + (-2) + 9 + 22 + 4 + 19 - 23 = 45).

Малко по-кратък начин, по който можем да направим същото нещо, е следният:
int
query(
int
left
,
int
right) {
int
idxL
=
getLeaf(left)
,
idxR
=
getLeaf(right)
;
if
(idxL
=
=
idxR)
return
tree[idxL]
;
int
sum
=
tree[idxL]
+
tree[idxR]
;
while
(idxL
+
1
!
=
idxR) {
if
(idxL
%
2
=
=
0
) sum
+
=
tree[idxL
+
1
]
;
if
(idxR
%
2
=
=
1
) sum
+
=
tree[idxR
-
1
]
;
idxL
/
=
2
,
idxR
/
=
2
;
}
return
sum
;
}
Тук идеята е, че ако idxL и idxR не са деца на един и същ връх (братя), то:
  • ако idxL е ляво дете, то ще добавим към сумата и десния му брат (който е с индекс idxL + 1)
  • ако idxR е дясно дете, то ще добавим към сумата и левия му брат (който е с индекс idxR - 1)

Строене

За да построим сегментно дърво от N елемента, можем или да ползваме N на брой пъти функцията update() (за сложност O(N∙log(N))), или да сме по-умни и да построим дървото от долу нагоре за О(N). Идеята е, че можем да поставим на най-долното ниво началните числа, а след това да обходим нивата едно по едно нагоре (докато стигнем до най-горното), правейки всеки връх да е равен на сбора на децата си:
void
buildTree(
int
*
values
,
int
valueCount) { memset(tree
,
0
,
sizeof
(tree))
;
for
(
int
i
=
0
;
i
<
valueCount
;
i
+
+
) tree[getLeaf(i)]
=
values[i]
;
for
(
int
node
=
getLeaf(
0
)
-
1
;
node
>
0
;
node
-
-
) tree[node]
=
tree[node
*
2
+
0
]
+
tree[node
*
2
+
1
]
;
}

Разменяне на ъпдейт и куери

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

Това става като "разменим" (до голяма степен) функциите query() и update(). Във върховете в най-долното ниво отново ще пазим числата, както са си в масива. В нивата над тях, обаче, този път ще пазим колко трябва да "добавим" към всяко число в поддървото на дадения връх. В началото всички върхове от по-горните нива ще са равни на нула. Когато направим ъпдейт на интервал, трябва да променим корените на поддърветата, които изцяло попадат стриктно в интервала (отново - взимайки най-големите, за да достигнем желаната O(log(N)) сложност).
int
query(
int
idx) { idx
=
getLeaf(idx)
;
int
sum
=
0
;
while
(idx) { sum
+
=
tree[idx]
;
idx
/
=
2
;
}
return
sum
;
}
void
update(
int
left
,
int
right
,
int
delta) {
int
idxL
=
getLeaf(left)
,
idxR
=
getLeaf(right)
;
if
(idxL
=
=
idxR) { tree[idxL]
+
=
delta
;
return
;
} tree[idxL]
+
=
delta
,
tree[idxR]
+
=
delta
;
while
(idxL
+
1
!
=
idxR) {
if
(idxL
%
2
=
=
0
) tree[idxL
+
1
]
+
=
delta
;
if
(idxR
%
2
=
=
1
) tree[idxR
-
1
]
+
=
delta
;
idxL
/
=
2
,
idxR
/
=
2
;
} }
void
buildTree(
int
*
values
,
int
valueCount) { memset(tree
,
0
,
sizeof
(tree))
;
for
(
int
c
=
0
;
c
<
valueCount
;
c
+
+
) tree[getLeaf(c)]
=
values[c]
;
}

Двумерни и многомерни сегментни дървета

Подобно на индексните дървета, и сегментните дървета могат да бъдат двумерни или многомерни. Ще покажем как би изглеждала структурата за 2D, като разширението за повече измерения е аналогично.

В стандартния вариант за двумерно сегментно дърво ъпдейтът ще е за една клетка (row, col), докато куерито ще е за под-правоъгълник от масива, дефиниран от {(row1, col1), (row2, col2)}. Тъй като ъпдейтът за всяко от измеренията е по O(log(N)), то за да направим ъпдейт на двумерно индексно дърво ще ни е нужно O(log(N)∙log(N)) = O(log2(N)). По-общо, за K-мерно дърво сложността ще бъде O(logK(N)).
?И при двумерно сегментно дърво няма проблем да направим модификацията, в която ъпдейтът е за под-правоъгълник, а куерито - за единична клетка.
Идеята е, че всеки елемент от двумерното сегментно дърво ще бъде отделно (едномерно) сегментно дърво. Трикът с представянето на идеално балансирано дърво в масив продължава да работи - просто сега масивът ще е двумерен. Едното измерение обхождаме както бихме обходили и едномерно сегментно дърво. Вместо да вземаме стойностите директно от масива, обаче, в двумерния вариант пускаме куери в под-дърветата.

Това като код изглежда по следния начин:
void
update(
int
row
,
int
col
,
int
delta) {
for
(
int
idxRow
=
row
+
TREE_SIZE
/
2
;
idxRow
>
0
;
idxRow
/
=
2
) {
for
(
int
idxCol
=
col
+
TREE_SIZE
/
2
;
idxCol
>
0
;
idxCol
/
=
2
) { tree[idxRow][idxCol]
+
=
delta
;
} } }
long
long
query(
int
row
,
int
col1
,
int
col2) {
int
idxL
=
col1
+
TREE_SIZE
/
2
;
int
idxR
=
col2
+
TREE_SIZE
/
2
;
if
(idxL
=
=
idxR)
return
tree[row][idxL]
;
long
long
sum
=
tree[row][idxL]
+
tree[row][idxR]
;
while
(idxL
+
1
!
=
idxR) {
if
(idxL
%
2
=
=
0
) sum
+
=
tree[row][idxL
+
1
]
;
if
(idxR
%
2
=
=
1
) sum
+
=
tree[row][idxR
-
1
]
;
idxL
/
=
2
,
idxR
/
=
2
;
}
return
sum
;
}
long
long
query(
int
row1
,
int
col1
,
int
row2
,
int
col2) {
int
idxL
=
row1
+
TREE_SIZE
/
2
;
int
idxR
=
row2
+
TREE_SIZE
/
2
;
if
(idxL
=
=
idxR)
return
query(idxL
,
col1
,
col2)
;
long
long
sum
=
query(idxL
,
col1
,
col2)
+
query(idxR
,
col1
,
col2)
;
while
(idxL
+
1
!
=
idxR) {
if
(idxL
%
2
=
=
0
) sum
+
=
query(idxL
+
1
,
col1
,
col2)
;
if
(idxR
%
2
=
=
1
) sum
+
=
query(idxR
-
1
,
col1
,
col2)
;
idxL
/
=
2
,
idxR
/
=
2
;
}
return
sum
;
}
Ако забелязвате, вътрешното куери е същото като едномерната версия (само че стойностите само от row-тото сегментно дърво). Външното куери пък е почти същото, но вика вътрешното, вместо да индексира масива.

Минимум или максимум в интервал

Ако поддържаната функция е min() или max(), казваме, че структурата данни се казва RMQ (което идва от Range Minimum Query или Range Maximum Query). В темата за минимум в интервал ще разгледаме как чрез съвсем малка модификация на сегментното дърво, което показахме тук, можем да постигнем RMQ, което има куери и ъпдейт за O(log(N)).

Интервални дървета

Друго надграждане на тази структура позволява както куери, така и ъпдейт на интервал, за O(log(N)) и за двете операции. Тази структура се нарича Интервално Дърво и ще разгледаме по-нататък.

Пълни имплементации

Тук сме дали пълни имплементации на показаните неща в темата:

Задачи за тренировка

Можете да напишете чистата форма на структурата за да решите тренировъчната задача

IndexTrees

Training problems, informatika.bg

Author: Alexander Georgiev
Tags: Medium, Index Trees
Statement | Archive | Online Judge
IndexTrees.

Едно от възможните решения на задачата Sheep е с индексни дървета. Задачата Shoes пък изисква да пазите повече информация във всеки връх на сегментното дърво.

По-нататък ще разгледаме няколко задачи, комбиниращи друг алгоритъм със сегментно дърво като оптимизация - например някои по-сложни динамични или пък задачи, решавани с метода на помитащата права.

Референции

  1. Префиксни Масиви (www.informatika.bg)
  2. Индексни Дървета (www.informatika.bg)
  3. Минимум/Максимум в Интервал (www.informatika.bg)
  4. Интервални Дървета (www.informatika.bg)





За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.
предишна тема
версия за печат
следваща тема
Страницата е посетена 7615 пъти.

Предложете корекция

Selected text (if you see this, there is something wrong)

(Незадължително) E-mail за обратна връзка: