i have stuck on this spoj problem in which i have to calculate dominance of points e.g. a point (x1, y1) is said to be dominating another point (x2, y2) if x1>=x2 and y1>=y2 .

https://www.spoj.com/problems/DCEPC705/

my question is that how can i calculate this using binary index tree? this question was queued under the Binary index tree on a portal.

First, make coordinate compression to have 0 ≤

x,y<n. Now sort the points in increasing order ofx(order points with equalxin increasing order ofy). For any point the number of points, which are dominated by it, is equal to count of points behind current point in the list, whoseycoordinate is not greater thanycoordinate of current point. So iterate over sorted list and keep a binary indexed tree, which counts the number of points with givenycoordinate. The number of points, which are dominated byi-th point, is equal tosum(0,y_{i}), after getting the answer fori-th point add 1 at positioniof the tree.There are problem 961E - Tufurama and good tutorial for it