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)

-

Comments

Post a Comment

Popular posts from this blog

serialization - Convert Any type in scala to Array[Byte] and back -

i have following question: i have variable value in program declared value. i want convert value byte array.. how can serialize byte array , back? found examples related other types such double or int, not any. this should need. it's pretty similar how 1 in java. import java.io.{bytearrayinputstream, bytearrayoutputstream, objectinputstream, objectoutputstream} object serialization extends app { def serialise(value: any): array[byte] = { val stream: bytearrayoutputstream = new bytearrayoutputstream() val oos = new objectoutputstream(stream) oos.writeobject(value) oos.close stream.tobytearray } def deserialise(bytes: array[byte]): = { val ois = new objectinputstream(new bytearrayinputstream(bytes)) val value = ois.readobject ois.close value } println(deserialise(serialise("my test"))) println(deserialise(serialise(list(1)))) println(deserialise(serialise(map(1 -> 2)))) println(deserialise(seri
Read more

matplotlib support failed in PyCharm on OSX -

any idea how fix ? how can debug might problem ? not seem : https://youtrack.jetbrains.com/issue/py-15520 i in console: python 2.6.9 (unknown, jul 14 2015, 19:46:31) [gcc 4.2.1 compatible apple llvm 6.0 (clang-600.0.39)] on darwin >>> import matplotlib.pyplot plt matplotlib support failed the backend : >>> import matplotlib >>> print(matplotlib.rcparams['backend']) macosx
Read more

python - Matplotlib: TypeError: 'AxesSubplot' object is not callable -

i new programming please pardon me if rookie mistake. i writing python script have defined functions create subplots of distributions. i have slider widget end user change value of variables(mu , sigma) , see effect on distribution. here's code import numpy np print np.__version__ import scipy print scipy.__version__ scipy.stats import norm, lognorm, uniform import matplotlib print matplotlib.__version__ import matplotlib.pyplot plt matplotlib.widgets import slider, button, radiobuttons, checkbuttons #####calculating mean , standard deviation##### global mu_a1 mu_a1 = 1 global mu_b1 mu_b1 = 10 global mu_c1 mu_c1 = -13 global sigma_a1 sigma_a1 = 0.14 global sigma_b1 sigma_b1 = 1.16 global sigma_c1 sigma_c1 = 2.87 mu_x01 = -11 sigma_x01 = 1.9 #####_____##### #####generating random data##### a1 = 0.75*mu_a1 + (1.25 - 0.75)*sigma_a1*np.random.sample(10000) b1 = 8*mu_b1 + (12 - 8)*sigma_b1*np.random.sample(10000) c1 = -12*mu_c1 + 2*sigma_c1*np.random.sample(10000)
Read more