Logaritamska struktura i tournament stablo

Stare Lukine materijale počeo sam dijeliti u ovoj objavi, a sada nastavljam. Evo odakle smo (između ostalog) prije 10+ godina učili logaritamsku i tournament, kada su te stvari bile relativno nove, a dobri web materijali o njima rijetki ili nepostojeći:

Luka Kalinovčić: Logaritamska struktura i tournament stablo

Logaritamsku strukturu tako zovu samo u Hrvatskoj, vani je zovu Fenwick tree ili binary indexed tree. Nekad je to bio veliki hit (npr. u zadnjem zadatku na DMIH-u 2006.), a danas je uče već u osnovnoj školi. O naprednijim mogućnostima te strukture pisao sam u ovoj objavi.

Tournament stablo vani zovu segment treeViše o njemu, uključujući i operaciju ažuriranja intervala (lijeni tournament tj. tournament s propagacijom) kao i još neka proširenja možete naći npr. na sljedećim mjestima:

https://csacademy.com/lesson/segment_trees/

https://codeforces.com/blog/entry/15890

Komentiraj

Popunite niže tražene podatke ili kliknite na neku od ikona za prijavu:

WordPress.com Logo

Ovaj komentar pišete koristeći vaš WordPress.com račun. Odjava /  Izmijeni )

Google photo

Ovaj komentar pišete koristeći vaš Google račun. Odjava /  Izmijeni )

Twitter picture

Ovaj komentar pišete koristeći vaš Twitter račun. Odjava /  Izmijeni )

Facebook slika

Ovaj komentar pišete koristeći vaš Facebook račun. Odjava /  Izmijeni )

Spajanje na %s