[Problem] Number of points with coordinates greater than those of the current one

Revision en3, by nhtrnm, 2017-10-02 03:30:27

Given n ≤ 106 points with integer coordinates on a 2D plane, for each point compute the number of points with coordinates greater than those of the current one.

I can only think of a solution in which sorts the points using x coordinate, and then for every point count the number of points after it with greater y coordinate. That can be done by using Fenwick tree or segment tree.

Can we do better than that? Can we do something simpler without using a segment tree or Fenwick tree?

Tags data structures, 2d

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English nhtrnm 2017-10-02 03:30:27 8 Tiny change: 'Given $n<=10^6$ poin' -> 'Given $n \leq 10^6$ poin'
en2 English nhtrnm 2017-10-02 03:29:53 25 Tiny change: '6$ points on a 2D ' -> '6$ points with integer coordinates on a 2D '
en1 English nhtrnm 2017-10-02 03:28:48 565 Initial revision (published)