maha1192's blog

Dynamic 2D orthogonal range query
By maha1192, 12 years ago, In English

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.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Maybe you can use Range Tree on 2 Dimension plane

→ Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

You need solution for offline problem or online problem?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply