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

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

Сегментното дърво е двоично кореново дърво (...). Всеки връх на сегментното дърво отговаря за някакъв сегмент от масива, като сегментите на различни върхове в едно ниво не се пресичат. Затова се наричат и сегментни дървета :) Листата на дървото отговарят за единични сегменти - различните елементи на масива. Това, което се пази за всеки връх, винаги е свързано с конкретната цел, заради която построяваме сегментното. Така че, за да покажем как се построява и какво се пази във върховете, ще разгледаме следната стандартна задача. Нека имаме масив $A$ от $n$ числа. Заявките, които искаме да обработваме са следните:

  • заявки за търсене с параметри $ql$ и $qr$ - сумата на подмасив $\sum\limits_{i=ql}^{qr} A[i]$
  • заявки за обновяване с параметри $pos$ и $val$ - променяме стойността на някой елемент $A[pos]=val$

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


В сегментното дърво всеки връх освен листата има по две деца. Коренът отговаря за целия масив (в нашия случай за числата на позиции от 1 до 8). Съответно лявото му дете отговаря за лявата половина от числата (тези на позиции от 1 до 4), а дясното дете - за дясната половина (от 5 до 8). Така рекурсивно ще стигнем до листата. Сегментното дърво е рекурсивна структура от данни. На най-високо ниво, се използва идеята разделяй и владей върху дадения масив - ако връх отговаря за интервала $[l;r]$, то децата му отговарят за двете половинки $[l; {l+r \over 2}]$ и $[{l+r \over 2}+1; r]$, рекурсивно същото е за децата и техните деца и т.н. (това е разделяй частта). По-късно ще се убедим, че информацията за всеки връх, който не е листо, се получава от децата му - владей частта. Обикновено сегментното дърво се пази в един масив. Нека засега си мислим, че големината на масива е степен на двойката (за примера $8=2^3$). Ако означим с $n$ броя числа в масива, то нека $n=2^s$. Тогава лесно можем да сметнем общия брой върхове, които ще имаме в дървото - $1+2^1+2^2+...+2^s=$ $2^{s+1}-1=2n-1$. Това означава, че броя върхове, който ни трябва е линеен спрямо големината на масива.

Нека номерираме върховете отгоре-надолу по нива и отляво-надясно, като започнем с номер 1 при корена. С бутона "Покажи номерата" може да се види тази номерация на примера. Наблюдателните могат да забележат следната зависимост за номерата на връх и неговите деца. Ако върхът е с номер $k$, то лявото му дете е с номер $2k$, а дясното - $2k+1$. Затова се използва масив за запазване на сегментното дърво, защото лесно можем по номер на връх да се ориентираме за номерата на децата. Обратното, ако имаме връх с номер $k$, то баща му е с номер $[{x\over 2}]$.

Досега говорехме, че $n$ е степен на двойката. Какво правим в общия случай? Един лесен начин е да допълним масива до най-близката степен на двойката с нули. Това обаче е напълно излишно. Може да се забележи, че ако използваме същата зависимост за позициите на връх и неговите деца, няма да имаме проблеми. Единствено в последното ниво (това на листата) може да имаме дупки в номерацията, т.е. номера, на които не съответстват връхове. Но ако винаги ползваме рекурсивната дефиниция, това няма да създава проблеми. За да е по-ясно, вижте номерацията на върховете при сегментното дърво построено за 10 елемента, например. Един важен детайл е за броя върхове, които могат да ни трябват. Ако $n=2^s+4$, може да се види, че спазвайки номерацията, максималния номер, който ще ни трябва ще е $2^{s+1}+2^s+2^{s-1}+1=$ $(2n-8)+(n-4)+(n/2-2)+1=$ $3n+n/2-13>3n$. Както казахме, ако $n$ не е степен на двойката, последното ниво не е пълно. Ако най-близката $\ge$ степен на двойката e $2^s \le 2n$, то за да направим оценка за максималния брой върхове, можем да мислим, че го построяваме върху масив с $2^s$ елемента. Такова дърво би имало най-много $2.2^s-1 \lt 4n$ елемента. Затова обикновено в задачи, когато има максимално ограничение $MAXN$ за големината на масива с числата, за да няма големи разсъждения сегментното дърво се прави с големина $4.MAXN$. От сега нататък вече не налагаме ограничение за големината на масива $n$.

Нека означим масива за сегментното дърво с $tree$. Понеже разглеждаме сегментно дърво, което ще отговаря заявки за сума, то в масива за всеки връх ще пазим сумата на числата в масива, за които отговаря (...). При листата, тази стойност отговаря само за едно число. Нека сме на връх с номер $k$. Съответно лявото дете, което съдържа сумата на числата в лявата половина, ще е с номер $2k$, а дясното дете, което отговаря за сумата на дясната половина - $2k+1$. Тогава имаме следната лесна формула, за да сметнем стойността за върха $k$ - $tree[k]=tree[2k]+tree[2k+1]$. Това ни дава два лесни начина да построим сегментно дърво. Първият е итеративен - започваме да попълваме върховете в ред обратен на номерацията. По този начин, когато стигнем връх вече ще сме попълнили стойностите на децата му и ще можем по формулата да сметнем стойността му. Вторият начин, който ще покажем, е рекурсивен и следва рекурсивната дефиниция на структурата от данни:

Лесно се вижда, че функцията build_tree работи толкова пъти, колкото върхове има в сегментното дърво. Понеже броят на върховете е линеен относно големината на масива, то сложността, с която е построяването е линейна - $O(n)$.

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

  • заявки за обновяване с параметри $pos$ и $val$ - променяме стойността на някой елемент $A[pos]=val$

Нека помислим какво трябва да се промени след като $A[pos]=val$. Промяна настъпва при тези върхове на сегментното, които отговарят за сегмент, съдържащ позиция $pos$. Понеже интервалите на различните върхове от едно ниво не се пресичат, то тези върхове, където нещо трябва да се промени, са най-много колкото броя нива на дървото. Нещо, което досега не сме изяснили е колко са нивата. Понеже върховете във всяко следващо ниво нарастват двойно спрямо предходното (като изключим евентуално най-последното), то е ясно, че нивата са около $\log_{2}n$, т.е. малък брой върхове се променят. Оказва се, че има лесен начин да опишем променящите се върхове - това са всички върхове по пътя от корена до листото, което отговаря за интервала $[pos; pos]$.

Самата промяна, която настъпва е следната - отново трябва да изчислим сумата за всеки връх. Така, ако поправяме стойностите отдолу-нагоре, е достатъчно отново да сумираме за всеки връх, стойностите на лявото и дясното дете, за да получим актуалната сума след заявката. Отново има два начина да реализираме това - итеративен и рекурсивен. Итеративният начин започва от листото и се движи нагоре по бащите. За този начин трябва да запазим позицията на всяко листо, а катеренето нагоре по бащите е просто с целочислено делене на 2. Ние ще покажем рекурсивния начин, защото той е по-лесен за писане (макар и малко по-бавен) и по-полезен за бъдещите надграждания на сегментното дърво.

На всяка стъпка на рекурсията проверяваме дали листото, отговарящо за променения елемент е вляво или вдясно. А на обратния ход - смятаме наново сумата за всеки връх, през който сме минали, за да отразим променения елемент. Така всички върхове на сегментното дърво имат правилна стойност след изпълнение на функцията. Ясно е, че функцията работи колкото елемента се променят, т.е. със сложност $O(\log_{2}n)$. За по-добро разбиране е предоставен интерактивен пример за работата на рекурсията при заявка за промяна.


  • заявки за търсене с параметри $ql$ и $qr$ - сумата на подмасив $\sum\limits_{i=ql}^{qr} A[i]$

Нека да видим кои върхове ще са ни достатъчни, за да намерим сумата. Ясно е, че ако имаме два интервала, за които $[l_1;r_1] \subset [l_2;r_2] \subset [ql;qr]$, то ще се интересуваме от върха на по-широкия интервал $[l_2;r_2]$. Нека отново да направим като предното рекурсивно обхождане на дървото. Последното наблюдение показва, че при обхождането, когато стигнем връх, чийто интервал се съдържа в този на заявката, няма нужда да ходим повече надолу. По-сложното при тази заявка, е че може да се наложи да ходим и вляво, и вдясно от даден връх. Това е така, защото интервалът $[ql;qr]$ може да има елементи, както вляво, така и вдясно спрямо средата. Предоставяме реализация на описаното обхождане:

Тук сложността не е лесна за определяне, защото от всеки връх потенциално може да отидем и в двете му деца. Но всъщност с индукция по нивата може да се докаже, че за всяко ниво ще стъпим най-много в 4 върха. Защо се получава така? Очевидно този факт е изпълнен за първите две нива, които имат само по 1 и по 2 върха съответно. Нека допуснем, че твърдението е изпълнено за $k$-тото ниво. Ще го докажем за следващото. Ако в $k$-тото ниво сме стъпили в най-много 2 върха, то понеже от всеки от тях може да отидем най-много в по 2, то е изпълнено, че в следващото ниво ще стъпим най-много в 4 върха. Нека разглеждаме по-трудния случай, когато в $k$-тото ниво сме стъпили в три или четири върха. Да помислим какво ограничава броя върхове в следващото ниво? Оказва се, че с изключение на крайните върхове, от останалите няма как да продължим надолу. Щом сме в среден връх, това означава, че нашата заявка изцяло ще съдържа интервала, за който отговаря върха, защото трябва да отидем в по-ляв и в по-десен връх на същото ниво, а интервалът на заявката е непрекъснат. Нека за онагледяване да разгледаме заявка за сума на числата в интервала $[2;7]$ при $8$ елемента общо. На третото ниво ще стъпим и в четирите върха, които отговарят съответно за интервалите $[1;2]$, $[3;4]$, $[5;6]$ и $[7;8]$. Съответно при върховете, асоциирани с интервалите $[3;4]$ и $[5;6]$, не продължаваме надолу, точно поради факта, че интервалът на заявката $[2;7]$ изцяло ги съдържа (...).

Това, което получихме е силен резултат, защото показва, че използвайки рекурсивно обхождане за намиране на нужните върхове, ще стъпим най-много в $4.\log_2{n}$ върха. При по-внимателен анализ може да се забележи, че върховете, които ще включим за сумата са малко по-малко - $2.\log_2{n}$. Така получаваме същата сложност и на тази заявка - $O(\log_{2}n)$, но с по-тежка константа - 4. Отново може да се направи итеративна реализация, на която няма да се спираме в детайли. На кратко идеята отново е да тръгнем от крайното ляво и дясно листо, да ги движим едновремнно нагоре и да преценяваме кои интервали се включват, дали трябва да включим и някой долен връх. За по-добро онагледяване отново има интерактивен пример, който следва рекурсивната реализация на заявката за търсене на сума. Когато напускаме връх, до него се появава сумата на елементите, които участват в интервала на заявката.


Така получихме, че сегментното дърво поддържа промяна на един елемент и заявка за интервал за логаритмична сложност, поради което е ценна структура от данни. Също така лесно се построява сегментното дърво за линейно време. Аналогично може да се построи сегментно дърво, поддържащо и други заявки - за минимум, максимум, НОД, НОК, ..., като се запазят хубавите сложности на строене и заявки. За да разберем дали дадена функция може да се поддържа от сегментно дърво, трябва всъщност да си представим следната ситуация. Нека имаме връх, отговарящ за даден интервал, който има ляво и дясно дете и успешно сме се справили с лявата половина на интервал, както и с дясната. Въпросът е дали информацията, която ще сме попълнили в лявото и в дясното дете, можем да я "обединим" бързо, за да получим същата информация но за по-големия интервал, за който отговаря нашия връх. Пример за функция, която не може да се поддържа бързо от сегментно дърво, е ако имаме заявки за сумата от квадратите на броя срещания на всяка уникална стойност в подмасив. Едно естествено надграждане на заявката за промяна е да имаме еднотипна промяна на повече от един елемент наведнъж. В този случай се използва техниката lazy propagation, която може да разгледате в следващата тема за сегментни дървета.

Както казахме, обикновено сегментното дърво се построява върху масив, който естествено има не твърде голям брой елементи. Понякога обаче се налага да се построи сегментно дърво за доста голям сегмент. Тогава част от нещата са неприложими без промяна. Нека разглеждаме следната задача. Получаваме заявки от два типа:

  • заявки за добавяне на точка с координата $c$ върху положителната числова ос
  • заявки за намиране броя на точките с координати в интервала $[ql; qr]$

Ако може да обработваме заявките офлайн (т.е. първо да ги прочетем и след това да намерим отговорите) е достатъчно да компресираме координатите, с което да гарантираме, че не са твърде големи и да използваме сегментно дърво или sweep line. Нека обаче разглеждаме задачата в онлайн контекст (трябва да отговаряме на заявка веднага след като я получим). Може да си мислим, че ограничението за координатите на точките са от $1$ до $10^9$. Тогава се използват т.нар. динамични сегметни дървета. Наричат се по този начин, защото не е както при класическите сегметни дървета, които се построяват в началото и след това няма нови върхове, а точно обратното - няма никакво строене предварително, а това става динамично, малко по-малко.

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

Както се вижда в кода, за да е най-удобно, информацията за всеки връх на дървото е групирана в структура. Имаме глобален брояч curr за свободен индекс на нов връх. Смятането на tree[ind].cnt може да се направи като просто се увеличи старата стойност с 1. В кода е написано по по-дълъг начин, защото при по-сложна задача най-вероятно ще има нужда от такова нещо. Предоставен е интерактивен пример, където могат да се добавят нови точки и да се наблюдава как се добавят новите върхове. За да е по-плитко дървото, координатите, които се позволяват, са от 1 до 64.

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

Ясно е, че функциите запазват логаритмичната си сложност $O(\log_2{MAXNUM})$. Но тя е по-тежка от преди, защото вече зависи от максималната стойност, а не от броя елементи. В примерната задача $MAXNUM=10^9$, т.е. грубо функциите ще им трябват по около 30 стъпки всеки път, което не е много малко. Освен това работата им е леко по-тежка, защото индексите за ляво и дясно дете трябва да се гледат в паметта. Все пак това е един добър вариант, който използва, че макар целият сегмент да е голям, то на всяка заявка ще ѝ трябват да гледа грубо $\log_2{MAXNUM}$ върхове. Затова е приложима тази идея сегментното дърво да се построява динамично. От друга страна е хубаво да се прави оценка и на паметта при този вид дървета. Ако имаме $q$ заявки, ще ни трябва $O(q.log_2{MAXNUM})$ памет.