We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Interval trees are pretty complicated. I find arrays are easier, and a lot faster. If n is the number of points, consider a left-complete binary tree with n leaves. You can represent that in an array of size 2^(1 + ceil(log2(n))). Array element 1 is the root, and the children of element i are at 2*i and 2*i+1. At each element store the 4-long vector (for each quadrant) of counts of points in the subtree of that element. Each leaf node contains exactly one point. At every internal node, also store a "flip" parameter that says how that count needs to be permuted to reflect the X/Y operations that have been done on that subtree. When an X or Y query is made, traverse the tree and update the flip parameter of any node that is entirely contained in the query but whose parent is not contained.
Quadrant Queries
You are viewing a single comment's thread. Return to all comments →
Interval trees are pretty complicated. I find arrays are easier, and a lot faster. If n is the number of points, consider a left-complete binary tree with n leaves. You can represent that in an array of size 2^(1 + ceil(log2(n))). Array element 1 is the root, and the children of element i are at
2*iand2*i+1. At each element store the 4-long vector (for each quadrant) of counts of points in the subtree of that element. Each leaf node contains exactly one point. At every internal node, also store a "flip" parameter that says how that count needs to be permuted to reflect the X/Y operations that have been done on that subtree. When an X or Y query is made, traverse the tree and update the flip parameter of any node that is entirely contained in the query but whose parent is not contained.