Square tree - trees with multiple tree levels
I recently came across a new data structure called segment trees, and then read that it can be extended to two dimensions as well, but I could not find a good source to familiarize myself with its implementation details and other things. I would like to know about this in terms of using it in a programming competition and not in the area of graphics. Some problems that could be solved with this would also be helpful. Can anyone point me to a good source to read about this? Thanks to
source to share
Extending segment trees to multiple dimensions, especially in a programming competition, can be very difficult and time consuming.
If you need multiple dimensions, you should first learn about binary indexed trees and then try to extend them to multiple dimensions.
Binary indexed trees are a data structure that performs better than shard trees in some cases, and simply is not suitable in others.
Extending to multiple dimensions is trivial when using segmented trees.
You can find an article about them here .
You can find an issue here that can help you test your implementation .
source to share
I'm not sure if you can find more sources regarding this. I think he left people to understand how k-segment trees work. In your position, I would try to solve a problem that can be done with it. A simple example (and I know this query can be done in O (1) with some upfront process): the sum of a rectangular range. That is: a given matrix filled with numbers responds to queries requesting the sum of the sub-matrix. Here you can use one semgent tree to split the height and then at each node you create an additional segment tree for the sum based on the width. If you can do this, then you know everything there is to know about 2D. segmented trees. The next challenge would be to allow one item to be updated - this speeds up,since you need to use some "art" to propagate changes correctly (think of some kind of caching inside the segment tree). :)
source to share