I was told my whole informatics career that quad-tree operations were all logarithmically proportional to the size of the tree's range. This is true for insertion and point queries, but it is not true for range queries. In the worst case, a range query will recurse down to 1x1 blocks around the edge of your rectangle -- and there are O(sqrt(S)) of these.
No comments:
Post a Comment