Segmenttipuu

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 6. lokakuuta 2016 tarkistetusta versiosta . vahvistus vaatii 41 muokkausta .

Segmenttipuu on tietorakenne , jonka avulla voit löytää assymptotiikkaa varten jonkin assosiatiivisen funktion arvon mielivaltaisesta taulukon segmentistä . Yleisimmin käytetyt funktiot ovat summa, tulo, maksimi ja minimi. $f$ $a[i],a[i+1],\pisteet ,a[j]$ $O(\log n)$ $f$

Rakenteen kuvaus

Segmenttipuu on juurtunut puu, jonka lehdet ovat alkuperäisen taulukon elementtejä, ja muilla kärjeillä on kullakin 2 lasta. Jokaiselle kärjelle on määritetty väli, joka on sen lapsien välien liitto (jos kärjessä on lapsia), tai väli, joka sisältää tietyn taulukon elementin (lehdille). Lisäksi jokaiselle kärjelle tallennetaan jonkin assosiatiivisen funktion arvo tietyllä aikavälillä. Tällä puulla on logaritminen korkeus, koska tasojen lukumäärä ei ylitä $f$ $\log _{2}n$

Segmenttipuu muistissa

Olkoon taulukossamme elementtejä : . $a$ $n$ $a[0],a[1],\dots,a[n-1]$

Valitaan sellainen . Täydennetään oikealla olevaa taulukkoamme neutraaleilla elementeillä niin, että sen pituus on yhtä suuri kuin . Sitten taulukon elementteihin rakennetun segmenttipuun tallentamiseksi tarvitsemme joukon soluja . $h$ $2^{h}\geq n$ ${\näyttötyyli 2^{h))$ $a$ $b$ $2^{h+1}$

Emme käytä nollasolua taulukossa , ja solut ensimmäisestä -: nteen vastaavat binääripuun huippuja vastaavilla numeroilla. Yleensä segmenttipuun kärkien numerointia käytetään läpikulkujärjestyksessä leveys , eli puun juurella on numero 1 ja kärjen vasemmalla ja oikealla pojilla numerolla on numerot ja vastaavasti. Tällä numeroinnilla kärki, jonka numero on at , vastaa segmenttiä , eli numero tallennetaan soluun . $b$ ${\näyttötyyli (2^{h+1}-1)}$ $v$ $2v$ $2v+1$ $2^{k}+u$ ${\displaystyle 0\leq u<2^{k))$ $[u2^{hk};(u+1)2^{hk}-1]$ $b[2^{k}+u]$ $f(a[u2^{hk}],a[u2^{hk}+1],\dots ,a[(u+1)2^{hk}-1])$

Artikkelissa käytetään tätä segmenttipuun kärkien numerointia. Vaihtoehtoisesti voit numeroida kärjet syvyystraversal järjestyksessä , jolloin kärjen vasemmalla ja oikealla pojilla on numerot ja , missä on kärkeä vastaava segmentti . Samanaikaisesti, jos rakennat segmenttipuun heti alkuperäisen taulukon mukaan etkä laajenna sitä pituuteen (sellaisen puun kaikki segmentin pituudet eivät ole kahden potenssit eivätkä kaikki lehdet sijaitse maksimissaan syvyys), niin kaikki taulukon solut riittävät sen tallentamiseen . Tallennettaessa puuta, jonka kärjet on numeroitu leveyden läpikulkujärjestyksessä, taulukon pituus voi olla . $v$ $v+1$ $v+2(\lfloor {\dfrac {L+R}{2}}\rfloor -L+1)$ $[L;R]$ $v$ $a$ ${\näyttötyyli 2^{h))$ $2n$ $b$ $b$ $4n-4$

Segmenttipuun rakentaminen

Alla on C++-koodi rekursiiviselle funktiolle segmenttipuun muodostamiseksi taulukon elementtien summalle . Puun rakentamisen monimutkaisuus on toimia. $\mathop {\rm {build}}$ $a$ $O(2^{h})=O(n)$

tyhjä rakenne () { rakentaa(1, 0, (1 << h) - 1); } void build(int v, int L, int R) { jos (L == R){ b[v] = a[L]; } else { int C = (L + R)/2; rakentaa (v * 2, L, C); rakentaa (v * 2 + 1, C + 1, R); b[v] = b[v*2] + b[v*2 + 1]; } }

Segmenttipuu yhdellä muutoksella

Elementin muuttaminen

Muutetaan arvoa . Sitten meidän on päivitettävä arvot soluissa , , ,..., . Siten se ryhtyy toimiin elementin muuttamiseksi. $a[i]$ $b[2^{h}+i]$ $b[2^{h-1}+i/2]$ $b[2^{h-2}+i/4]$ $b[1]$ $O(h)=O(\log(n))$

Alla on C++-koodi rekursiiviselle proseduurille segmenttipuun päivittämiseksi summalle , kun lähdetaulukon -. elementti muuttuu . $\mathop {\rm {päivitys}}$ $i$ $a$

mitätön päivitys (int i, int uusi arvo) { päivitys(1, 0, (1 << h) - 1, i, uusiArvo); } void update (int v, int L, int R, int i, int uusi arvo) { jos (L == R){ b[v] = uusi Arvo; a[i] = uusi Arvo; } else { int C = (L + R)/2; if (i <= C){ päivitys(v * 2, L, C, i, uusiArvo); } else { päivitä(v * 2 + 1, C + 1, R, i, uusiArvo); } b[v] = b[v*2] + b[v*2 + 1]; } }

Funktion laskeminen segmentille

Funktion laskemiseen elementeistä käytetään seuraavaa rekursiivista funktiota argumenteista , joka laskee funktion arvon segmentille . Tässä on sellainen puun kärkipiste, että solu sisältää segmentin funktion arvon . $f$ $a[l],a[l+1],\cdots ,a[r]$ ${\mathhop {{\rm {count))))$ $v, L, R, l, r$ $f$ $[L;R]\cap[l;r]$ $v$ $b[v]$ $f$ $[L;R]$

Jos segmentit ja eivät leikkaa, niin vastaus on yhtä suuri kuin funktion neutraali elementti (0 summalle, 1 tulolle, maksimille, minimille). $[L;R]$ $[l;r]$ $f$ $-\infty$ $+\infty$

Jos , niin vastaus on . $[L;R]\subset [l;r]$ $b[v]$

Muussa tapauksessa jaamme segmentin kahtia asettamalla . Pelkistetään ongelma funktion laskemiseen segmenteille ja . Sitten vastaus on . $[L;R]$ $C=\lfloor {\dfrac {L+R}{2}}\rfloor$ $f$ $[L;C]\cap[l;r]$ $[C+1;R]\cap[l;r]$ $f({\rm {count}}(2v,L,C,l,r),{\rm {count}}(2v+1,C+1,R,l,r))$

Näin ollen segmentin funktion laskenta supistuu funktion laskemiseen joitakin segmenttejä vastaavien taulukon elementeistä . $[l;r]$ $b$ $[2^{k}u;2^{k}(u+1)-1]$

Osoitetaan, että kun funktio lasketaan, saadaan tulokset. Jokaisella syvyydellä palautamme arvon enintään kahdesta puun kärjestä. Päinvastoin, oletamme, että niitä on vähintään kolme. Mutta sitten kaksi kutsua kahdesta naapuripisteestä voitaisiin korvata yhdellä kutsulla heidän yhteiseltä vanhemmalta. Siksi kullakin syvyydellä palautamme korkeintaan kaksi arvoa. Rakenteesta johtuen puun korkeus ei ylitä . Siksi palautuksia ei tehdä enempää. $2\log(n)$ $\log(n)$ $2\log(n)$

Samanlainen päättely osoittaa, että yhdessä puun kyselyssä ohitamme korkeintaan kärjet. $4\log(n)$

Alla on C++-koodi segmentin summan laskemiseen . $[l;r]$

int getSum(int l, int r) { return getSum(1, 0, (1 << h) - 1, l, r); } int getSum(int v, int L, int R, int l, int r) { jos (L > r || R < l){ paluu 0; } jos (l <= L && R <= r){ paluu b[v]; } int C = (L + R)/2; return getSum(v * 2, L, C, l, r) + getSum(v * 2 + 1, C + 1, R, l, r); }

Segmenttipuu intervallin muokkauksella

Oletetaan, että haluamme muuttaa ei yhden taulukon solun arvoa , vaan koko intervallin (esimerkiksi kasvattaa kaikkien solujen arvoja väliltä annetulla numerolla ). Silloin pelkän taulukon tallentaminen ei riitä. Kuitenkin segmenttipuut, jotka pystyvät laskemaan summan ja maksimin, voidaan toteuttaa tallentamalla kaksi samanpituista taulukkoa ja toteuttamalla muutosoperaatio rekursiivisesti. $a$ $a[l],\cdots ,a[r]$ $X$ $b$

Segment Tree for Sum (RSQ)

Tallennamme taulukoita samalla osoitteella kuin taulukko (katso yllä). $summa$ $add$ $b$

Rekursiivinen menettely koostuu segmentin kaikkien elementtien arvon kasvattamisesta numerolla . voi olla sekä positiivista että negatiivista. Tässä on puun kärkipiste, jossa solu sisältää välin kaikkien elementtien summan . ${\rm {muokkaa))(v,L,R,l,r,X)$ $[L;R]\cap[l;r]$ $X$ $X$ $v$ $summa[v]$ $[L;R]$

Alla on menettelykoodi C++:ssa. ${\rm {muokkaa))$

void muokata(int l, int r, int X) { muokata(1, 0, (1 << h) - 1, l, r, X); } void muokata(int v, int L, int R, int l, int r, int X) { jos (L > r || R < l){ palata; } jos (l <= L && R <= r){ summa[v] += X* (R - L + 1); add[v] += X; } else { int C = (L + R)/2; modifioi (v*2, L, C, l, r, X); modifioi (v * 2 + 1, C + 1, R, l, r, X); summa[v] = summa[v * 2] + summa[v * 2 + 1] + summa[v] * (R - L + 1); } }

Rekursiivista funktiota segmentin summan laskemiseksi muutetaan seuraavasti. Hänellä on vielä yksi argumentti , joka kuvaa sitä, kuinka paljon sinun on lisättävä kaikkia segmentin numeroita summaa laskettaessa. ${\rm {getSum))$ $[L;R]\cap[l;r]$ $additive$ $[L;R]$

int getSum(int l, int r) { return getSum(1, 0, (1 << h) - 1, l, r, 0); } int getSum(int v, int L, int R, int l, int r, int additive) { jos (L > r || R < l){ paluu 0; } jos (l <= L && R <= r){ palautussumma[v] + lisäys * (R - L + 1); } int C = (L + R)/2; return getSum(v * 2, L, C, l, r, additive + add[v]) + getSum(v * 2 + 1, C + 1, R, l, r, additiivinen + additiivinen [v]); }

Toiminnan monimutkaisuus on . ${\rm {muokkaa))$ ${\näyttötyyli {\rm {count}}}$ $O(\log(n))$

Suurin segmenttipuu (RMQ)

Kuten edellisessä tapauksessa, tallennamme taulukot ja . Menettelyllä on sama merkitys ja samat argumentit. $max$ $add$ ${\rm {muokkaa))$

void muokata(int l, int r, int X) { muokata(1, 0, (1 << h) - 1, l, r, X); } void muokata(int v, int L, int R, int l, int r, int X) { jos (L > r || R < l){ palata; } jos (l <= L && R <= r){ max[v] += X; add[v] += X; } else { int C = (L + R)/2; modifioi (v*2, L, C, l, r, X); modifioi (v * 2 + 1, C + 1, R, l, r, X); max[v] = std::max(max[v * 2], max[v * 2 + 1]) + add[v]; } }

Rekursiivinen funktio segmentin maksimin laskemiseksi toteutetaan samalla tavalla kuin summan segmenttipuufunktio. ${\rm {getMax}}$ $[L;R]\cap[l;r]$ ${\rm {getSum))$

int getMax(int l, int r) { return getMax(1, 0, (1 << h) - 1, l, r, 0); } int getMax(int v, int L, int R, int l, int r, int additive) { jos (L > r || R < l){ paluu -INF; // Miinus ääretön, ts. numero, joka on varmasti pienempi kuin mikään segmenttimme numero. Jos esimerkiksi kaikki luvut eivät ole negatiivisia, voit laittaa INF = 0. } jos (l <= L && R <= r){ paluu max[v] + lisäaine; } int C = (L + R)/2; int max1 = getMax(v * 2, L, C, l, r, additive + add[v]); int max2 = getMax(v * 2 + 1, C + 1, R, l, r, additive + add[v]); return std::max(max1, max2); }

Toiminnan monimutkaisuus on . ${\rm {muokkaa))$ ${\rm {getMax}}$ $O(\log(n))$

RMQ:n ratkaiseminen harvalla taulukolla

Myös RMQ-ongelma voidaan ratkaista käyttämällä Sparse-taulukkoa. Tämän tietorakenteen avulla voit löytää segmentin maksimi-/minimiarvot O(1):ssä esikäsittelyllä O(n log n) ajassa.

Esikäsittely:

Merkitse - maksimi/minimi segmentissä välillä - . Taulukko voidaan täyttää dynaamisesti seuraavasti: ${\mathop {{\rm {f))))[i,k]$ $i$ $i+2^{k}-1$ ${\mathop {{\rm {f))))[i,k]$

1) ; ${\mathop {{\rm {f))))[i,0]=a[i]$

2) tai vastaavasti. ${\mathop {{\rm {f))))[i,k]=\max({\mathop {{\rm {f))))[i,k-1],{\mathop {{\rm {f}}}}[i+2^{{k-1}},k-1])$ ${\mathop {{\rm {f))))[i,k]=\min({\mathop {{\rm {f))))[i,k-1],{\mathop {{\rm {f}}}}[i+2^{{k-1}},k-1])$

Laskeminen:

Vastaus väliin on (vastaavasti ), jossa lg on kahden maksimiteho, joka ei ylitä . $[l,r]$ $\max({\mathop {{\rm {f))))[l,lg],{\mathop {{\rm {f))))[r-2^{{lg}}+1,lg] )$ $\min({\mathop {{\rm {f))))[l,lg],{\mathop {{\rm {f))))[r-2^{{lg}}+1,lg] )$ $rl+1$

Esimerkki:

Tarkastellaan vaihteluväliä 1 - 5. Sille sopiva kahden maksimiteho on kaksi, mutta se ei kata koko aluetta, vaan vain osan 1 - 4. Tämän segmentin maksimi saadaan vertaamalla arvoja f[1,2] ja f[2,2] (maksimiarvot segmenteillä 1-4 ja 2-5).

O(1)-ratkaisu O(N)-esikäsittelyllä ja muistilla

Tällaista ratkaisua varten riittää pelkistää RMQ-ongelma LCA -ongelmaksi rakentamalla karteesinen puu muodon elementeistä eli - avain, - prioriteetti. Prioriteetit on järjestettävä alhaalta ylöspäin, eli se elementti, jolla on pienin . Ilmeisesti tällainen puu on helppo rakentaa :lle , koska kaikki avaimet, jotka meillä on, ovat järjestyksessä (nämä ovat taulukon elementtien peräkkäisiä indeksejä). $(i,a[i])$ $i$ $a[i]$ $a[i]$ $PÄÄLLÄ)$

Sen jälkeen vastaus mihin tahansa pyyntöön on kahden kärjen ja :n LCA . LCA-indeksi sijaitsee , koska karteesinen puu avaimen mukaan on binääripuu. Koska karteesinen puu on prioriteettikeko , samalla solmulla on alhaisin prioriteetti (elementtiarvo) kaikista $(l,a[l])$ $(r,a[r])$ $[l;r]$ $[l;r]$

Esikäsittelyn ja muistin LCA - ongelmaan tunnetaan useita mahdollisia ratkaisuja . Tällainen ratkaisu on asymptoottisesti optimaalinen. $O(1)$ $PÄÄLLÄ)$

Linkit

Katso myös

Fenwick puu
Luettelo tietorakenteista (puista)

Puu (tietorakenne)
Binäärihakupuu Puu (graafiteoria) puun rakenne
Binääripuut	binäärinen puu T-puu
Itsetasapainottavat binaaripuut	AA puu AVL puu Puna-musta puu Splay-puu puu sakkoilla karteesinen puu Fibonacci puu B-puu T-puu
B-puut	2-3-puu B⁺-puu B*-puu B x -puu UB puu 2-3-4 puu (a,b)-puu tanssiva puu
etuliite puita	suffiksi puu Pakattu etuliitepuu Kolmiosainen hakupuu
Avaruuden binaarinen osiointi	k-ulotteinen puu VP-puu
Ei-binääripuut	Quadtree oktreen Harva Voxel Octree eksponentiaalinen puu PQ puu
Avaruuden hajottaminen	R-puu Hilbert R-puu R+-puu R*-puu X-puu M-puu Fenwick puu Segmenttipuu
Muut puut	pino hash puu sormipuu metrinen puu Päällystyspuu BK-puu Kaksiketjuinen puu iDistance Linkistä leikattu puu LSM puu
Algoritmit	Leveys ensimmäinen haku Ensimmäinen syvyyshaku DSW-algoritmi kattava puu protokolla