2D orthogonal range query

Revision en1, by DanceTheTragonDrainer, 2019-09-13 15:50:49

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English DanceTheTragonDrainer 2019-09-13 15:50:49 561 Initial revision (published)