Szegmens fa

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2016. október 6-án felülvizsgált verziótól ; az ellenőrzéshez 41 szerkesztés szükséges .

A szegmensfa egy olyan adatstruktúra , amely lehetővé teszi valamilyen asszociatív függvény értékének megtalálását egy tömb tetszőleges szegmensén aszimptotikus célokra . A leggyakrabban használt függvények az összeg, a szorzat, a maximum és a minimum. $f$ $a[i],a[i+1],\pontok,a[j]$ $O(\log n)$ $f$

A szerkezet leírása

A szegmensfa egy gyökeres fa, melynek levelei az eredeti tömb elemei, a többi csúcsnak pedig 2-2 gyermeke van. Minden csúcshoz hozzá van rendelve egy intervallum, amely a gyermekei intervallumainak uniója (ha a csúcsnak vannak gyermekei), vagy egy intervallum, amely a tömb egy adott elemét tartalmazza (a levelek esetében). Ezenkívül minden csúcshoz egy adott intervallumon valamilyen asszociatív függvény értéke tárolódik. Ennek a fának logaritmikus magassága lesz, mivel a szintek száma nem haladja meg $f$ $\log _{2}n$

Szegmensfa a memóriában

Legyenek tömbünk elemei : . $a$ $n$ $a[0],a[1],\pontok,a[n-1]$

Válasszunk olyat . A jobb oldali tömbünket egészítsük ki semleges elemekkel úgy, hogy hossza egyenlő legyen . Ezután a tömb elemeire épített szegmensfa tárolásához szükségünk van egy cellatömbre . $h$ $2^{h}\geq n$ ${\displaystyle 2^{h))$ $a$ $b$ $2^{h+1}$

A tömbben nem használjuk a nulla cellát , és az elsőtől a -edikig lévő cellák a bináris fa csúcsainak felelnek meg a megfelelő számokkal. Általában a szegmensfa csúcsainak számozását a szélességben való bejárás sorrendjében használjuk , azaz a fa gyökerének száma 1, a számmal rendelkező csúcs bal és jobb fia pedig számokkal , ill. Ezzel a számozással az at számot tartalmazó csúcs megfelel a szegmensnek , vagyis a szám a cellában lesz eltárolva . $b$ $(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])$

A cikkben a továbbiakban a szegmensfa csúcsainak ezt a számozását használjuk. Alternatív megoldásként számozhatja a csúcsokat a mélységi bejárás sorrendjében , ekkor a csúcs bal és jobb oldali fiai és számok lesznek , ahol a csúcsnak megfelelő szakasz . Ugyanakkor, ha egy szegmensfát azonnal az eredeti tömbnek megfelelően épít , és nem bővíti ki egy hosszúságúra (egy ilyen fában nem minden szegmenshossz lesz kettő hatványa, és nem minden levél helyezkedik el a maximumon mélység), akkor a tömb összes cellája elegendő lesz a tárolására . Egy fa tárolásakor, amelynek csúcsai a szélességi bejárás sorrendjében vannak számozva, a tömb hossza elérheti a -t . $v$ $v+1$ $v+2(\lfloor {\dfrac {L+R}{2}}\rfloor -L+1)$ $[L;R]$ $v$ $a$ ${\displaystyle 2^{h))$ $2n$ $b$ $b$ $4n-4$

Szegmensfa felépítése

Az alábbiakban egy rekurzív függvény C++ kódja található, amely egy tömb elemeinek összegére szegmensfát hoz létre . A fa felépítésének összetettsége a cselekvésekben rejlik. $\mathop {\rm {build}}$ $a$ $O(2^{h})=O(n)$

void build() { build(1, 0, (1 << h) - 1); } void build(int v, int L, int R) { ha (L == R){ b[v] = a[L]; } más { int C = (L + R)/2; build(v * 2, L, C); épít(v*2+1,C+1,R); b[v] = b[v * 2] + b[v * 2 + 1]; } }

Szegmensfa egyetlen módosítással

Az elem módosítása

Változtassuk meg az értékét . Ezután frissítenünk kell az értékeket a , , ,..., cellákban . Így lépéseket fog tenni az elem megváltoztatására. $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))$

Az alábbiakban a C++ kód egy rekurzív eljáráshoz, amely frissíti a szegmensfát az összeghez, amikor a forrástömb -edik eleme megváltozik . $\mathop {\rm {update}}$ $én$ $a$

érvénytelen frissítés (int i, int newValue) { update(1, 0, (1 << h) - 1, i, newValue); } void update(int v, int L, int R, int i, int newValue) { ha (L == R){ b[v] = újÉrték; a[i] = újÉrték; } más { int C = (L + R)/2; if (i <= C){ update(v * 2, L, C, i, newValue); } más { frissítés(v * 2 + 1, C + 1, R, i, újÉrték); } b[v] = b[v * 2] + b[v * 2 + 1]; } }

Függvény kiszámítása egy szegmenshez

Függvény elemekből történő kiszámításához a következő argumentumokból származó rekurzív függvényt használjuk , amely kiszámítja a függvény értékét a szegmenshez . Itt van egy olyan fa csúcs, hogy a cella tartalmazza a szegmens függvényének értékét . $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]$

Ha a és szakaszok nem metszik egymást, akkor a válasz egyenlő a függvény semleges elemével (0 az összegre, 1 a szorzatra, a maximumra, a minimumra). $[L;R]$ $[l;r]$ $f$ $-\infty$ $+\infty$

Ha , akkor a válasz az . $[L;R]\subset [l;r]$ $b[v]$

Ellenkező esetben a szegmenst a beállítással kettéosztjuk . Csökkentsük a problémát egy függvény kiszámítására a és szegmensekre . Akkor a válasz az . $[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))$

Így egy függvény számítása egy szegmensre redukálódik egy függvény kiszámítására a tömb egyes szegmenseinek megfelelő elemeiből . $[l;r]$ $b$ $[2^{k}u;2^{k}(u+1)-1]$

Mutassuk meg, hogy a függvény kiszámításakor megkapjuk az eredményeket. Minden mélységben legfeljebb két fa csúcsából adunk vissza értéket. Éppen ellenkezőleg, azt feltételezzük, hogy legalább három van belőlük. De akkor két szomszédos csúcsból érkező két hívást felválthatna a közös szülőjük egy hívása. Ezért minden mélységnél legfeljebb két értéket adunk vissza. Az építkezés miatt a fa magassága nem haladja meg a . Ezért nem történik több visszaküldés. $2\log(n)$ $\log(n)$ $2\log(n)$

Hasonló érvelés azt mutatja, hogy a fa egyetlen lekérdezésében legfeljebb csúcsokat kerülünk ki. $4\log(n)$

Az alábbiakban látható a C++ kód egy szegmens összegének kiszámításához . $[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) { if (L > r || R < l){ visszatérés 0; } if (l <= L && R <= r){ return b[v]; } int C = (L + R)/2; return getSum(v * 2, L, C, l, r) + getSum(v * 2 + 1, C + 1, R, l, r); }

Szegmens fa intervallum módosítással

Tegyük fel, hogy nem a tömb egy cellájának , hanem az egész intervallumnak az értékét szeretnénk megváltoztatni (például növeljük az intervallum összes cellájának értékét egy adott számmal ). Ekkor nem elég csak a tömb tárolása . Az összeg és a maximum kiszámítására képes szegmensfák azonban megvalósíthatók két azonos hosszúságú tömb tárolásával és a változtatási művelet rekurzív végrehajtásával. $a$ $a[l],\cdots ,a[r]$ $x$ $b$

Segment Tree for Sum (RSQ)

A tömböket ugyanazzal a címzéssel fogjuk tárolni , mint a tömböt (lásd fent). $összeg$ $add$ $b$

A rekurzív eljárás abból áll, hogy a szegmens összes elemének értékét számmal növeljük . lehet pozitív és negatív is. Itt van egy olyan fa csúcs, amelyben a cella tartalmazza az intervallum összes elemének összegét . ${\rm {módosítás))(v,L,R,l,r,X)$ $[L;R]\cap[l;r]$ $x$ $x$ $v$ $összeg[v]$ $[L;R]$

Alább látható az eljárás kódja C++ nyelven. ${\rm {módosítás))$

void modify(int l, int r, int X) { módosít(1, 0, (1 << h) - 1, l, r, X); } void modify(int v, int L, int R, int l, int r, int X) { if (L > r || R < l){ Visszatérés; } if (l <= L && R <= r){ összeg[v] += X* (R - L + 1); add[v] += X; } más { int C = (L + R)/2; módosít(v * 2, L, C, l, r, X); módosít(v * 2 + 1, C + 1, R, l, r, X); összeg[v] = összeg[v * 2] + összeg[v * 2 + 1] + összeadás[v] * (R - L + 1); } }

A szegmens összegének kiszámítására szolgáló rekurzív függvény a következőképpen módosul. Van még egy érve , amely azt jellemzi, hogy mennyivel kell növelni a szegmens összes számát az összeg kiszámításakor. ${\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 additív) { if (L > r || R < l){ visszatérés 0; } if (l <= L && R <= r){ visszatérési összeg[v] + additív * (R - L + 1); } int C = (L + R)/2; return getSum(v * 2, L, C, l, r, additív + add[v]) + getSum(v * 2 + 1, C + 1, R, l, r, additív + add[v]); }

A műveletek összetettsége . ${\rm {módosítás))$ ${\rm {count}}$ $O(\log(n))$

Maximális szegmensfa (RMQ)

Az előző esethez hasonlóan a tömböket és a . Az eljárásnak ugyanaz lesz a jelentése és ugyanazok az érvek. $max$ $add$ ${\rm {módosítás))$

void modify(int l, int r, int X) { módosít(1, 0, (1 << h) - 1, l, r, X); } void modify(int v, int L, int R, int l, int r, int X) { if (L > r || R < l){ Visszatérés; } if (l <= L && R <= r){ max[v] += X; add[v] += X; } más { int C = (L + R)/2; módosít(v * 2, L, C, l, r, X); módosít(v * 2 + 1, C + 1, R, l, r, X); max[v] = std::max(max[v * 2], max[v * 2 + 1]) + add[v]; } }

A szegmens maximumának kiszámítására szolgáló rekurzív függvény az összeg szegmensfa függvényéhez hasonlóan valósul meg . ${\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 additív) { if (L > r || R < l){ return -INF; // Mínusz végtelen, i.e. egy szám, amely minden bizonnyal kisebb, mint bármely szám a szegmensünkben. Például, ha minden szám nem negatív, akkor INF = 0 lehet. } if (l <= L && R <= r){ return max[v] + adalék; } int C = (L + R)/2; int max1 = getMax(v * 2, L, C, l, r, additív + add[v]); int max2 = getMax(v * 2 + 1, C + 1, R, l, r, additív + add[v]); return std::max(max1, max2); }

A műveletek összetettsége . ${\rm {módosítás))$ ${\rm {getMax}}$ $O(\log(n))$

RMQ megoldása ritka táblával

Az RMQ probléma is megoldható a Sparse táblával. Ez az adatstruktúra lehetővé teszi, hogy megtalálja a szegmens maximumát / minimumát O(1)-ben, előfeldolgozással O(n log n) idő alatt.

Előfeldolgozás:

Jelölje a - maximumot/minimumot a től ig terjedő szakaszon . Egy tömb dinamikusan a következőképpen tölthető ki: ${\mathop {{\rm {f))))[i,k]$ $én$ $i+2^{k}-1$ ${\mathop {{\rm {f))))[i,k]$

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

2) ill . ${\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])$

Számítás:

Az intervallumra a válasz ( illetve ), ahol lg a kettő maximális hatványa, amely nem haladja meg a -t . $[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$

Példa:

Az 1-től 5-ig terjedő tartományt vesszük figyelembe. A ráférő kettő maximális teljesítménye kettő, de nem fedi le a teljes tartományt, hanem csak egy 1-től 4-ig terjedő részt. Ezen a szegmensen a maximumot az értékek összehasonlításával kaphatjuk meg. f[1,2] és f[2,2] (maximum 1-4 és 2-5 szegmenseken).

O(1) megoldás O(N) előfeldolgozással és memóriával

Egy ilyen megoldáshoz elegendő az RMQ-problémát az LCA -problémára redukálni úgy, hogy a form elemeiből egy derékszögű fát készítünk , azaz - kulcs, - prioritás. A prioritásokat alulról felfelé kell rendezni, azaz a legkisebb értékű elemet . Nyilvánvaló, hogy egy ilyen fát könnyű felépíteni a -hoz , mivel az összes kulcsunk rendezett (ezek a tömbelemek egymást követő indexei). $(i,a[i])$ $én$ $a[i]$ $a[i]$ $TOVÁBB)$

Ezt követően minden kérésre a válasz két csúcs és a . Az LCA-index a -ban található , mivel a Descartes-fa kulcsonként bináris fa. Tekintettel arra, hogy a derékszögű fa egy prioritáshalom , ugyanannak a csomópontnak lesz a legalacsonyabb prioritása (elemértéke) az összes közül $(l,a[l])$ $(r,a[r])$ $[l;r]$ $[l;r]$

Számos lehetséges megoldás ismert az előfeldolgozással és a memóriával kapcsolatos LCA problémára . Az ilyen megoldás aszimptotikusan optimális. $O(1)$ $TOVÁBB)$

Linkek

Lásd még

Fenwick fa
Adatstruktúrák listája (fák)

Fa (adatstruktúra)
Bináris keresőfa Fa (gráfelmélet) fa szerkezet
Bináris fák	bináris fa T-fa
Önkiegyensúlyozó bináris fák	AA fa AVL fa Vörös-fekete fa Splay fa fa bírságokkal karteziánus fa Fibonacci fa B-fa T-fa
B-fák	2-3-fa B⁺-fa B*-fa B x -fa UB fa 2-3-4 fa (a,b)-fa táncoló fa
előtag fák	utótag fa Tömörített előtag fa hármas keresőfa
A tér bináris particionálása	k-dimenziós fa VP fa
Nem bináris fák	Quadtree oktfa Ritka Voxel Octree exponenciális fa PQ fa
A tér felosztása	R-fa Hilbert R-fa R+-fa R*-fa X-fa M-fa Fenwick fa Szegmens fa
Más fák	halom hash fa ujjfa metrikus fa Bevonat fa BK-fa Kétláncú fa iDistance Link-vágott fa LSM fa
Algoritmusok	Szélesség első keresés Mélységi első keresés DSW algoritmus átívelő fa protokoll