20.500.12556/RUL-161751 Prilagoditev podatkovnih struktur za učinkovite dinamične intervalne poizvedbe na več dimenzij Adapting data structures for efficient dynamic interval queries to multiple dimensions V diplomskem delu se osredotočamo na problem dinamične intervalne poizvedbe in ga prilagodimo za več dimenzij. Predstavimo podatkovni strukturi segmentno drevo in Fenwickovo drevo, ki omogočata reševanje problema v logaritemskem času. Predstavimo lastnosti funkcij, ki jih lahko uporabimo s strukturama, in pokažemo, da morajo biti asociativne in da morajo imeti nevtralen element. Za Fenwickovo drevo potrebuje funkcija še obratno operacijo. Pri prilagoditvi na več dimenzij se izkaže, da je segmentno drevo lahko element segmentnega drevesa. S pomočjo te lastnosti lahko rešujemo problem v več dimenzijah. Enako se da narediti tudi za Fenwickovo drevo. Merili smo čas izvajanja lastne implementacije segmentnega drevesa in Fenwickovega drevesa v Javi za poizvedovanje in posodabljanje in smo ga primerjali s časom delovanja dveh naivnih metod. Čas smo merili tudi za dvodimenzionalni in tridimenzionalni problem. Obe drevesi se izkažeta za učinkoviti za posodabljanje in poizvedbe v eni ali več dimenzijah, je pa Fenwickovo drevo nekoliko hitrejše. The focus of the thesis is adapting the problem of dynamic range querying to multiple dimensions. We explain the already existing solutions, namely the segment tree and the Fenwick tree, which can do range queries and point updates in logarithmic time. After that we show that they can be used for any associative function, which has an identity element. For the Fenwick tree, the function also needs to have an inverse. We then explain that a segment tree can be an element inside of a segment tree and use this property to solve the problem of dynamic range querying in multiple dimensions. The same is done for the Fenwick tree. We conclude with timing the updating and querying operations on the segment and Fenwick tree, as well as two naïve solutions in one, two and three dimensions, and show that both structures are efficient in updating and querying, but the Fenwick tree performs better. segmentno drevo Fenwickovo drevo intervalne poizvedbe segment tree Fenwick tree interval query true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2024-09-13 12:25:20 2024-09-13 12:25:24 2024-11-04 12:28:55 0000-00-00 00:00:00 2024 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 37504 213581315 Luci_Aljaz_-_Prilagoditev_podatkovnih_struktur_za_ucinkovite_dinamicne_intervalne_poizvedbe_na_v.pdf Luci_Aljaz_-_Prilagoditev_podatkovnih_struktur_za_ucinkovite_dinamicne_intervalne_poizvedbe_na_v.pdf 1 F08CF605F1ECCC1F96C262A32DCD1AE7 8658b36a8066e795379d98c769c2a7dd21b2eee322a59d6e1230495023e78705 6c73787a-71ba-11ef-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=190733 Fakulteta za računalništvo in informatiko 0 0 0