Lõikude puu

Lõikude puu on struktuurilt kuhjaga sarnane tasakaalustatud kahendpuu kujuline andmestruktuur, mis salvestab mingit infot lõikude kohta. Selle struktuur on staatiline: seda ei saa peale konstrueerimist muuta. Tihti ehitatakse lõikude puu mingi arvujada peale, kus infot hoitakse selle jada elementide vahemike kohta.

Lõikude puu kasutab ${\displaystyle O(N)}$ mälu ja selle saab konstrueerida ${\displaystyle O(N)}$ ajaga. Lõikude puuga saab lahendada vahemikust miinimumi pärimise (ingl Range Minimum Query, RMQ) probleemi ${\displaystyle O(\log N)}$ ajaga.^[1]

Struktuur

Lõikude puul vastab iga tipu lõik oma alamate lõikude ühendile. Üldiselt vastavad lehtede lõigud mingi suurema terviklõigu tükeldusele, ehk lehtede lõigud on ühisosadeta ja järjestatud vasakult paremale. Tulemusena on igal sügavusel olevate tippude lõigud paarikaupa ühisosata ja lisaks on iga tipu enda vahemik tükeldamata tervik. Just need omadused teevad lõikude puust pärimise kiireks.

Operatsioonid

Lõikude puul saab ${\displaystyle O(\log N)}$ ajaga käsitleda aluseks olevas jadas üksiku elemendi väärtuse muutumist. Sellisel juhul tuleb lihtsalt uuendada vastav leht ja kõik tipud, mis jäävad teele sellest lehest puu juureni.

Kui lõikude puu tipud salvestavad vastava lõigu miinimumi, siis on võimalik pärida ${\displaystyle O(\log N)}$ ajaga suvalise alusjada vahemiku miinimumi järgneva rekursiivse algoritmi abil:

• Kui tipu vahemik on päritud vahemiku sees, siis väljasta tipu miinimum
• Kui vasak alamtipp omab ühisosa päritava lõiguga, siis tee rekursiivne päring sellelt alamtipult
• Kui parem alamtipp omab ühisosa päritava lõiguga, siis tee rekursiivne päring sellelt alamtipult
• Väljasta rekursiivsetelt päringutelt saadud vastuste miinimum

Algoritm omab ülalmainitud ajalist keerukust, kuna igal sügavusel on ülimalt kaks tippu, millest tehakse rekursiivne kutse. See kehtib, kuna peale esimest hargnemist on igal sügavamal päringul kas üks tipp täielikult päritava vahemiku sees või teine täielikult sellest väljas.^[2]

Täiendused

Lõikude puule eksisteerib täiendusi, mis võimaldavad selle abil rohkem probleeme lahendada. Mõned näited:

Laisa laienemise meetod

Laisk laienemine (ingl Lazy Propagation) on lähenemine, kus lõigu uuendamise päringutel lükatakse tippude uuendamise edasi hetkeni, kus nende andmeid reaalselt vaja läheb. Meetodi töötamiseks peavad lõigu uuendamise päringud olema korrapärased, näiteks kõigile sama uue väärtuse andmine või kõigi suurendamine mingi sama konstandi võrra. Sisuliselt tehakse võimalikult kõrgetele tippudele märgistus et nendel tuleb see uuendus teha. Tulevikus kui tipu väärtust vaja läheb rakendatakse tipule märgistatud uuendus ja saadetakse märgistus tipu alamatele edasi. See võimaldab lõikude uuendamist teha ${\displaystyle O(\log N)}$ ajaga.^[3][4]

Püsiv lõikude puu

Püsiv lõikude puu (ingl Persistent Segment Tree) on lõikude puu variant, mis võimaldab teha ajaloolisi päringuid, näiteks mis oli mineviku ajahetkel t mingi lõigu elementide miinimum. Tasub tähele panna, et mingi üksiku lehe väärtuse uuenemisel tuleb lõikude puus uuendada ainult ${\displaystyle O(\log N)}$ lehti. Püsiv lõikude puu loob peale iga uuendust uue versiooni lõikude puust, aga iga versioon lisab ainult ${\displaystyle O(\log N)}$ tippu, mis vastavad uuendatud teele jäävatele tippudele. Uue tipu mitteuuendatud alamatipp asub mingis varasemas versioonis, ehk uuema versiooni tipud võivad omada varasemate versioonide tippe alamatena. See trikk võimaldab ${\displaystyle O(\log N)}$ aja ja mälu kuluga uuendamist ja ${\displaystyle O(\log N)}$ ajaga ajaloolist päringut.^[3]

Viited

1. S. Halim, F.Halim (2013). Competitive Programming 3 The New Lower Bound of Programming Contests, lk 55.
2. Data Structures Programmeerimisvõistlused 2017 Kasutatud 26.04.2018
3. Data Structures, Advanced Concepts Programmeerimisvõistlused 2017 Kasutatud 26.04.2018
4. A Recursive approach to Segment Trees, range sum queries & lazy propagation LeetCode Kasutatud 26.04.2018