Индексни Дървета

Index Trees

В тази тема ще разгледаме една от най-полезните структури данни, които можете да срещнете по състезания – индексни дървета. Те предоставят ефективен начин за търсене на сума (или друга комутативна функция) в интервал. Поради голямата си популярност, по-често ще я срещате като оптимизация на друг алгоритъм, отколкото сама по себе си.
Автор: Александър Георгиев

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

Наименование

Индексните дървета можете да срещнете също като "Дървета на Фенуик" (кръстени на автора им), "Lowest-Bit Index Trees" (в следствие на имплементацията), или "Binary Indexed Trees (BIT)". Все пак, те не трябва да се бъркат със сегментните дървета, които ще разгледаме в следващата тема - те могат да се ползват вместо индексни, но като имплементация и идея на работа са различни.

Намиране на най-младшия бит

За да извършваме операциите в индексни дървета бързо, ще трябва да знаем как да намираме най-младшия сетнат бит (lowest bit) на едно двоично число. В темата за побитови операции показахме един начин за това, като само споменахме друг, по-кратък такъв, а именно:
int
lowestBit(
int
num) {
return
num
&
-
num
;
}
Защо това работи? В модерните компютри целите числа се представят с една техника, наричана 2-s complement. При нея, за да получим отрицателната версия на някакво число X, правим побитов NOT (invert на двоичните цифри) на числото (X = ~X), след което прибавяме 1 (X = X + 1). С други думи, следните два реда са еквивалентни:
X
=
-
X
;
X
=
~
X
+
1
;
Нека, например, X = 42. Двоичното представяне на 42(10) е 00101010(2), докато неговото отрицателно, -42(10) е 11010101(2) (за простота тук ползваме 8-битово представяне). Наистина:
00101010(2) = 42(10) 11010101(2) = ~42(10) 11010110(2) = ~42(10) + 1
Какво би станало, ако AND-нем побитово 42 с неговото отрицателно? Ще получим число с един единствен сетнат бит - а имено, най-младшият бит на 42!

Можем да се уверим, че това работи и за числа, където най-младшият бит е на по-далечна позиция, както и когато представянето е 32-битово:
00000000000000011110001001000000(2) = 123456(10) 11111111111111100001110110111111(2) = ~123456(10) 11111111111111100001110111000000(2) = ~123456(10) + 1 = -123456(10) 00000000000000011110001001000000(2) = 123456(10) & 11111111111111100001110111000000(2) = -123456(10) = 00000000000000000000000001000000(2) = 64(10)

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

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

Строене

Строенето на индексно дърво от N елемента става със сложност O(N∙log(N)).

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

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

Търсене

Търсенето в индексно дърво е със сложност O(log(N)). Можете да забележите, че е малко по-бавно отколкото при префиксните масиви (които позволяваха сложност O(1)), но пък бързината на ъпдейта много често компенсира това.

Идея и имплементация

Първо ще отбележим, че както и при префиксния масив, не можем да "добавяме" и "изтриваме" елемент между два други.
!Индексните дървета работят за произволна комутативна функция (сума, произведение, xor, …), която има обратна функция. За простота ще покажем как работи за сума, като относително лесно се променя за която и да е друга.
Вместо това, ако предварително знаем колко най-много елемента ще имаме, можем да запазим фиктивни позиции за тях, като ги инициализираме с някаква стойност, която не влияе на търсенето. Например, бихме ползвали нула за функции като сума и xor, или едно за умножение. За да "добавим" елемент, всъщност ще променим стойността му от дефолтната на новата. За да "изтрием" елемент ще върнем неговата стойност до дефолтната му. Тоест ни интересува единствено операцията "променяне на елемент", като с нея можем да симулираме добавяне и премахване.

Цел

Имаме списък с N елемента и искаме бързо да можем да ги променяме и отговаряме на въпроси "Колко е сумата в интервала [left, right]?".

Представяне

Индексното дърво представлява масив с N + 1 елемента (ще оставим нулевия елемент празен за простота по-нататък):
int
tree[MAX
+
1
]
;
Всеки елемент на този масив отговаря за сумата на под-интервал от дадения списък от числа. Елементът с индекс idx пази сумата на 2z числа, където z е броят най-младши нули преди първата единица в двоичния запис на idx. По-конкретно, това са елементите в интервала [idx - 2z + 1, idx].

Например елементът с индекс 24(10) = 11000(2) от индексното дърво има три най-младши нули преди първата си единица, следователно пази сумата на 23 = 8 елемента в интервала [17, 24], както можете да видите на следната схема:

32
16
824
4122028
26101418222630
135791113151719212325272931
1234567891011121314151617181920212223242526272829303132
В схемата горе всеки индекс се среща точно по веднъж и е показано кои елементи сумира.


Нека разгледаме следния списък с числа: (42, 13, 17, 1, -18, 3, -2, 9, 22, 4, 19, -23, 12, 5, 7, 0, -10, -8, 6). Индексното дърво, пазещо този списък с числа, би изглеждало по следния начин:
11116
658
7342212
552-15626101714-1818
421173-185-2722919111213715-1017619
4213171-183-2922419-2312570-10-86
12345678910111213141516171819

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

За да променим елемент на даден индекс, трябва да променим всички "покриващи" го интервали. Например, за да променим с delta стойността на елемента, на позиция 6, трябва да променим елементите 6, 8, и 16. За да променим пък 9, трябва да променим 9, 10, 12, и 16. За 13 бихме променили 13, 14, и 16.

Какво е общото между тях? Нека разгледаме двоичните им представяния:
6(10) = 00000110(2) 9(10) = 00001001(2) 13(10) = 00001101(2) 8(10) = 00001000(2) 10(10) = 00001010(2) 14(10) = 00001110(2) 16(10) = 00010000(2) 12(10) = 00001100(2) 16(10) = 00010000(2) 16(10) = 00010000(2)
Забелязахте ли каква е логиката? Всеки път най-дясната единица се движи наляво, докато стигне до нула, затривайки всички единици по пътя си. Но това е просто добавяне на най-младшия бит на числото към самото число! Следователно, можем да правим ъпдейт на индексното дърво със следната функция:
void
update(
int
idx
,
int
delta) {
for
(
;
idx
<
=
MAX
;
idx
+
=
(idx
&
-
idx)) tree[idx]
+
=
delta
;
}

Търсене

Как можем да питаме за сумата на числата в интервал [left, right] от дадения масив?
!Точно това изваждане е причината да искаме да има "обратна" функция - в случая изваждане за сума. Ако индексното дърво пазеше произведение, щяхме да ползваме деление; ако пазеше XOR щяхме да ползваме отново XOR (тя е обратна на себе си); и т.н.
Ако имаме начин, да намерим сумата на всички числа с индекси до right, включително, с някаква функция query(int idx), то лесно можем да намерим сумата в [left, right]: това е просто query(right) - query(left - 1).
Индексните дървета правят именно това - позволяват бързо да се намери сумата (или някаква друга функция) в интервал от нула до даден индекс.
int
query(
int
left
,
int
right) {
return
query(right)
-
query(left
-
1
)
;
}
В случая сме си запазили 0-та да е фиктивен елемент (тоест 1 ≤ left ≤ right ≤ N), за да не се налага да правим проверки дали left == 0.

Нека, отново, разгледаме как можем да намерим сумата на всички числа до някакви индекси. За 6, това би била сумата на числата, пазени в 6 и 4. За 9, бихме взели 9 и 8. За 13, бихме сумирали 13, 12, и 8.

Разглеждайки двоичните им записи, този път е по-лесно да видим какво се случва:
6(10) = 00000110(2) 9(10) = 00001001(2) 13(10) = 00001101(2) 4(10) = 00000100(2) 8(10) = 00001000(2) 12(10) = 00001100(2) 8(10) = 00001000(2)
Тук е очевидно, че просто махаме битовете един по един, започвайки от най-младшите. Това можем да направим със следната функция:
int
query(
int
idx) {
int
sum
=
0
;
for
(
;
idx
>
0
;
idx
-
=
(idx
&
-
idx)) sum
+
=
tree[idx]
;
return
sum
;
}
Найс, а?

Строене

За да построим дърво от N елемента, можем да ползваме N на брой пъти функцията update() (за сложност O(N∙log(N))).

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

С малка хитрост можем да направим структурата така, че да ъпдейтваме цял интервал, като можем да питаме само за един елемент. Ако например искаме да добавим стойността delta към всеки елемент в интервала [left, right], бихме могли да постигнем това като добавим delta на позиция left (и покриващите я интервали), и после я извадим от позиция right + 1 (и покриващите я интервали).
int
values[MAX]
;
int
tree[MAX
+
2
]
;
int
query(
int
idx) {
int
res
=
values[idx
-
1
]
;
for
(
;
idx
>
0
;
idx
-
=
(idx
&
-
idx)) res
+
=
tree[idx]
;
return
res
;
}
void
update(
int
idx
,
int
delta) {
for
(
;
idx
<
=
MAX
;
idx
+
=
(idx
&
-
idx)) tree[idx]
+
=
delta
;
}
void
update(
int
left
,
int
right
,
int
delta) { update(left
,
delta)
;
update(right
+
1
,
-
delta)
;
}
Тук масивът values[] пази първоначалните стойности, докато индексното дърво (tree[]) указва колко трябва да бъде добавено към всеки индекс.

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

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

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

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

Реално същото нещо имахме и при префиксния масив. Тъй като там сложността на куерито беше O(1), то за двумерния вариант ставаше O(1∙1), което остава O(1).

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

Това като код изглежда по следния начин:
int
tree[MAX
+
1
][MAX
+
1
]
;
void
update(
int
x1
,
int
y1
,
int
val) {
for
(
int
x
=
x1
;
x
<
=
MAX
;
x
+
=
(x
&
-
x))
for
(
int
y
=
y1
;
y
<
=
MAX
;
y
+
=
(y
&
-
y)) tree[x][y]
+
=
val
;
}
int
query(
int
x1
,
int
y1
,
int
x2
,
int
y2) {
int
ret
=
0
;
for
(
int
x
=
x2
;
x
>
0
;
x
-
=
(x
&
-
x)) {
for
(
int
y
=
y2
;
y
>
0
;
y
-
=
(y
&
-
y)) ret
+
=
tree[x][y]
;
for
(
int
y
=
y1
-
1
;
y
>
0
;
y
-
=
(y
&
-
y)) ret
-
=
tree[x][y]
;
}
for
(
int
x
=
x1
-
1
;
x
>
0
;
x
-
=
(x
&
-
x)) {
for
(
int
y
=
y2
;
y
>
0
;
y
-
=
(y
&
-
y)) ret
-
=
tree[x][y]
;
for
(
int
y
=
y1
-
1
;
y
>
0
;
y
-
=
(y
&
-
y)) ret
+
=
tree[x][y]
;
}
return
ret
;
}

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

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

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

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

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

Тази структура данни стана популярна в най-чистия си вид чрез задачата Mobiles от IOI 2001, в която се искаше да се напише просто двумерно индексно дърво. След това има редица задачи, които искат малко или много същото, например UFOs в Timus, която пък е тримерно индексно, или Ambitious Experiment, която е едномерно такова (но трябва да се сетите как да го ползвате).

Преди тях можете да напишете чистата форма на задачата в тренировъчната задача

IndexTrees

Training problems, informatika.bg

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

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

Представяне чрез две дървета

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

Референции

  1. Префиксни Масиви (www.informatika.bg)
  2. Сегментни Дървета (www.informatika.bg)
  3. Интервални Дървета (www.informatika.bg)
  4. Original Paper by Fenwick (psu.edu)
  5. Range updates with Fenwick Tree (wordpress.com)
  6. Range Queries and Fenwick Trees (tumblr.com)




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

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

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

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