### maha1192's blog

By maha1192, 9 years ago,

Hi! I'm searching for a data structure, which efficiently offers the following two operations. On points in a 2D plane.

1) Add a point to the structure.

2) Count the number of points in a given rectangle, which is paralell to x and y axis.

Could anyone tell me if such data structure exists, or even better give me a linik to a simmilar problem on.

• +6

 » 9 years ago, # |   +1 Maybe you can use Range Tree on 2 Dimension plane
 » 9 years ago, # |   +6 You need solution for offline problem or online problem?
•  » » 9 years ago, # ^ |   0 First all all thanks for reply! I thought of the online problem, but I also know the insert order of the points beforehand, so the offline problem is also sufficient. If there exists a more efficient solution for the offline problem, please tell me this one.thanks a lot
•  » » » 9 years ago, # ^ |   +3 look at this paper: Range Searching.
•  » » » » 9 years ago, # ^ |   0 Thank's a lot! @ the others do you have a task on codeforces, where this is used!
 » 9 years ago, # |   0 how you decide that point is parallel to X-axis or Y-axis ....... i think any point is parallel to every axis
•  » » 9 years ago, # ^ |   0 a point, i think has no definition of "paralell". I mean the query rectangles sides are paralell to the axis
 » 9 years ago, # | ← Rev. 2 →   0 Finally up to my thought, its possible to add a new point(offline problem) in a 2d range tree by modifying sums in O( log^2 n ). Please tell me if you know any better approach? Queries can than be done in O( log n ) or O( log^2 n ).
 » 5 years ago, # |   0 Hi, do you have any idea where a problem like this exists in online judge? I am trying to solve this problem http://www.spoj.com/problems/ARNAB4/ however I got file size limit exceeded I am quite sure about my algorithm and wanted to test it. Any help would be appreciated!