algorithm - Faster Queries in plane -

problem have support q queries of set of n 2-d points in cartesian plane lying in [0,m]x[0,m]. points given in advance.

each query ask me count number of points enclosed in rectangle (x1,y1)*(x2,y2). (axis aligned rectangle).

constraints
0 < m < 10000

i want know more algorithms used. can perform these queries more efficiently using information points , queries given in advance , coordinates of points bounded etc.

variant: instead of n points begin with, can add n axis-aligned rectangular patches of points n add operation in our data structure , answer same queries. [lazy segment trees kind of approach].

this classic 2d binary indexed tree problem. binary indexed tree can give how many dots in rectangle (0,0) (x,y), if want find out how many dots in rectangle indicated (x1,y1) , (x2,y2), first have find coordinates of other 2 corner points of rectangle. let pul, pur, pbl, pbr 4 corner points of rectangle representing upper left corner, upper right corner, bottom left corner , bottom right corner. using inclusion-exclusion logic number of dots enclosed in rectangle is.

q(p) // query on 2d-bit point p gives how many dots in       // rectangle represented (0,0) , (p.x, p.y) result = q(pur)-q(pul)-q(pbr)+p(pbl)