DanceTheTragonDrainer's blog

2D orthogonal range query
By DanceTheTragonDrainer, history, 5 years ago, In English

Given N points in 2-D plane and Q queries. In each query you are given a rectangle (aligned with x,y axes) defined by the points x1, y1, x2, y2 where (x1, y1) is the lower left corner and (x2, y2) is the upper right corner, find the number of points inside the rectangle. Points on rectangle are considered inside.

Constraints : 1 ≤ N ≤ 100 000 1 ≤ Q ≤ 100 000 0 ≤ xi, yi ≤ 100 000 0 ≤ x1 < x2 ≤ 100 000 0 ≤ y1 < y2 ≤ 100 000

Does anyone have a link to this question or any implementation.

Thanks. DanceTheTragonDrainer.

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

»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Sort points by y coordinate and add them to fenwick tree by x coordinate. In fenwick tree store vectors of y coordinates. To get numbers of points in rectangle [0, x], [0, y] use upper_bound(v.begin(), v.end(), y) — v.begin(). If this is hard to understand use segment tree of segment trees.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Tried solving this Problem, using simple 2D Fenwick tree using map<pair<int,int>,int> as tree. Also with order statistics implementation as given here, but both give TLE. Whereas, using Merge Sort tree gives AC. ( Merge sort tree is basically, a segment tree where each node of tree keeps sorted array of interval it manages. ). Aren't all these supposed to be $$$O(log^2(N))$$$ per query? Is there a large constant for BIT and Order Statistics tree?

    2D BIT attempt

    OST attempt

    Segment Tree AC

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

      You need to use vector with BIT.

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

        Okay. But even during the contest yesterday, I searched a lot and found a lot of blogs which said using map in 2d bit only uses $$$O(log(MaxX)log(MaxY))$$$ states, so why does it not work as expected? According to my expectations, $$$Q=10^5,log(10^5)=17$$$ so total running time should be $$$289*10^5$$$ which should easily fit in time limit.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 5   Vote: I like it +1 Vote: I do not like it

        Still gives TLE, here. Anything I might be doing incorrectly?

        UPD: Nevermind, I forgot that the update I use for bit $$$ x = x + x$$$&$$$ (-x) $$$ requires 1 based indexing, and input coordinates can be zero. After fixing indexing, I got an AC. Thanks a lot.

        As a side note, will this always be faster than a merge sort tree? Atleast for counting points in rectangle?

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 4   Vote: I like it +4 Vote: I do not like it

      The following is a similar solution based on segment tree of sorted arrays, but the nodes are sorted after adding all the N points, not using Merge Sort during the addition of each point.

      Segment Tree AC

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

Good username.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

A standard problem about the scanline with segment tree

→ Reply