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.
Quadrant Queries
Quadrant Queries
Sort by
recency
|
21 Discussions
|
Please Login in order to post a comment
Here is my solution in java, javascript, python, C ,C++, Csharp HackerRank Quadrant Queries Problem Solution
Here is the solution of Quadrant Queries Click Here
Here is problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-quadrant-queries-problem-solution.html
Python3 solution
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
and2*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.