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.
|
