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.

Maybe you can use Range Tree on 2 Dimension plane

You need solution for offline problem or online problem?

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

look at this paper: Range Searching.

Thank's a lot! @ the others do you have a task on codeforces, where this is used!

how you decide that point is parallel to X-axis or Y-axis ....... i think any point is parallel to every axis

a point, i think has no definition of "paralell". I mean the query rectangles sides are paralell to the axis

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 ).

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!