Fenwickův strom

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 1. března 2019; kontroly vyžadují 10 úprav .

Fenwick tree ( binární indexovaný strom , anglicky Fenwick tree , binární indexovaný strom , BIT) je datová struktura , která umožňuje rychle měnit hodnoty v poli a najít některé funkce z prvků pole. Poprvé popsal Ryabko B.Ya. v roce 1989. [1] Plná verze, kterou publikoval v angličtině v roce 1992. [2]

O dva roky později (v roce 1994) se objevil článek P. Fenwicka [3] , kde byla popsána stejná struktura, později nazvaná "Fenwick tree".

Fenwickův strom pro součet

Pro přirozené číslo budeme označovat maximálního dělitele , což je mocnina dvou (za jednotku považujeme i mocninu dvou). Je snadné vidět, že F ( n )= n −( n & ( n − 1)), kde & je bitový AND dvou celých čísel. Nechť naše pole má prvky: . Vybíráme pro které . K uložení stromu Fenwick pak potřebujete řadu prvků . Očíslujeme je od 1 do . Buňka uloží součet do buněk pole od do . $n$ $F(n)$ $n$ $A$ $n$ $a[1],a[2],\tečky,a[n]$ $k$ $2^{k}\geq n$ $b$ $2^k$ $2^k$ $b[t]$ $A$ $tF(t)+1$ $t$

Fenwickův strom pro součet podporuje 2 operace:

1) upravit pomocí argumentů a — změnit hodnotu -té buňky pole na číslo ( může být kladné nebo záporné). $N$ $X$ $N$ $A$ $X$ $X$

2) počítat s argumentem - najít součet čísel v buňkách pole od 1. do tis. $N$ $A$ $N$

Obě operace lze snadno realizovat v jednom cyklu.

upravit(N,X)

jeden)	i=N
2)	Zatímco i≤ $2^k$
2.1)	Zvětšit b[i] o X
2.2)	Zvýšit i o F(i)

počet (N)

1) res=0

2) i=N

3) Nashledanou $i>0$

3.1) Zvyšte res o b[i]

3.2) Snížit i o F(i)

4) Odpověď = res

Složitost obou operací je O(k) = O(log n). Stojí za zmínku, že pomocí operace count(N) můžeme obecně najít součet na libovolném segmentu se stejnou složitostí, protože pro ≠1 je přesně roven . $[l,r]$ $l$ $počet(r)-počet(l-1)$

Fenwick strom pro maximum

Fenwickův strom pro maximum podporuje následující operace:

1) upravte pomocí argumentů a — pokud je hodnota v th buňce pole menší než , napište do ní číslo . Jinak ponechte hodnotu tak, jak je. $N$ $X$ $N$ $A$ $X$ $X$

2) počítejte s argumenty a - najděte maximální počet v buňkách pole od -th do -th. $L$ $R$ $A$ $L$ $R$

K uložení stromu kromě pole pole použijeme pole a . V té buňce pole uložíme maximum na segment ; v th buňce pole - maximum na segmentu v a na segmentu v . $A$ $vlevo, odjet$ $že jo$ $t$ $vlevo, odjet$ $[tF(t)+1,t]$ $t$ $že jo$ $[t,t+F(t)-1]$ $t<2^k$ $[t,t]$ $t = 2^k$

Následuje realizace operací.

upravit(N,X)

1)a[N]=max(a[N],X)

2)i=N

3) Nashledanou $i\le2^k$

3.1)levý[i]=max(levý[i],X)

3.2) Zvýšit i o F(i)

4)j=N

5) Nashledanou $j>0$

5.1)vpravo[j]=max(vpravo[j],X)

5.2) Snížit j o F(j)

počet (L,R)

1) rozlišení = 0

2)i=L

3) Nashledanou $i +F(i)\le R$

3.1)res=max(res,right[i])

3.2) Zvýšit i o F(i)

4)res=max(res,a[i])

5)j=R

6) Nashledanou $j-F(j)\ge L$

6.1)res=max(res,left[j])

6.2) Snížit j o F(j)

7) Odpověď = res

Složitost operací = . $O(\log(n))$

Všimněte si, že pomocí Fenwickova stromu pro maximum nemůžete snížit hodnotu zaznamenanou v buňce. Pokud chcete, aby vaše datová struktura měla tuto schopnost, měli byste maximálně použít řezací strom .

Operace lze jednoduše upravit tak, aby Fenwickův strom našel nejen hodnotu maxima, ale i buňku, ve které je tohoto maxima dosaženo.

Poznámky

↑ Boris Ryabko. Rychlý sekvenční kód. // Zprávy Akademie věd SSSR : časopis. - 1989. - T. 306 , č. 3 . - S. 548-552 . (Ruština)
↑ Boris Ryabko. Rychlý on-line adaptivní kód (anglicky) // IEEE Trans.on Inform.Theory. - 1992. - Sv. 28 , č. 1 . - S. 1400-1404 .
↑ Peter M. Fenwick. Nová datová struktura pro kumulativní frekvenční tabulky // Software: Praxe a zkušenosti: časopis. - 1994. - Sv. 24 , č. 3 . - str. 327-336 . - doi : 10.1002/spe.4380240306 .

Odkazy

Ryabko B.Ya. "Rychlý sériový kód", Zprávy Akademie věd SSSR, svazek 306, číslo 3, s. 548--552; přeloženo do angličtiny jako rychlý online kód v sovětské matematice. Dokl. 39 (1989), No. 3, 533-537.
B.Ya Ryabko; Rychlý online adaptivní kód. IEEE Trans.on Inform.Theory, v.28, n 1, Jul 1992 pp. 1400 – 1404. http://boris.ryabko.net/ryabko1992.pdf
A. Lakhno Fenwick Tree . Kurz "Datové struktury", MTsNMO .
Implementace stromu Fenwick v C++ na e-maxx.ru
Implementace stromu Fenwick v Javě
Článek o stromu Fenwick na Habrahabru

Strom (datová struktura)
Binární vyhledávací strom Strom (teorie grafů) stromová struktura
Binární stromy	binární strom T-strom
Samovyrovnávací binární stromy	AA strom strom AVL Červeno-černý strom Rozvětvený strom strom s pokutami karteziánský strom Fibonacciho strom B-strom T-strom
B-stromy	2-3-strom B⁺-strom B*-strom B x -strom UB strom 2-3-4 strom (a,b)-strom tančící strom
předponové stromy	příponový strom Komprimovaný strom předpon Ternární vyhledávací strom
Binární dělení prostoru	k-rozměrný strom VP strom
Nebinární stromy	Čtyřstrom oktree Řídký Voxel Octree exponenciální strom PQ strom
Rozbití prostoru	R-strom Hilbertův R-strom R+-strom R*-strom X-strom M-strom Fenwickův strom Segmentový strom
Jiné stromy	halda hash tree prstový strom metrický strom Potahový strom BK-strom Dvouřetězový strom iVzdálenost Link-cut strom LSM strom
Algoritmy	Šířka první hledání Hloubka první hledání Algoritmus DSW protokol spanning tree