Given $N$ points in 2D plane, and each point has some value. Have to answer $Q$ queries of the form:

Given $x_1, x_2, y_1, y_2$, find sum of values of all points $(x,y)$ such that $x_1 \le x \le x_2$ and $y_1 \le y \le y_2$. $N$ and $Q$ are $\le 10^6$. Also it will be helpful if someone can provide implementation.

  • 1
    $\begingroup$ This seems like a standard question in computational geometry. What have you tried, and where did you get stuck? Note also that we are not going to provide any implementation. This is not the purpose of this site. $\endgroup$ – Yuval Filmus Jun 8 '17 at 16:15
  • $\begingroup$ I don't know how to solve it in sublinear time. $\endgroup$ – nequit Jun 8 '17 at 16:22
  • $\begingroup$ Try to use k-d trees or a similar data structure. $\endgroup$ – Yuval Filmus Jun 8 '17 at 16:24
  • $\begingroup$ How, can you provide any useful link? $\endgroup$ – nequit Jun 8 '17 at 16:31
  • $\begingroup$ You can find information on k-d trees and their applications to range search (which is your problem) on the web and in textbooks on computational geometry. I already gave you one link, namely Wikipedia. $\endgroup$ – Yuval Filmus Jun 8 '17 at 16:32

Possible solutions, if you're satisfied with fully offline solutions (all points and queries are known beforehand):

  1. If coordinates are small enough (e.g. they're integers between $0$ and $C$), you can precalculate summed area table. Precalculate in $O(C^2)$ and answer each query online in $O(1)$. Memory consumption would be $O(C^2)$.
  2. If they are not, you can use 2D segment tree with coordinate compression. Build the tree in $O(n \log n)$ (where $n$ is the number of points) and answer single query in $O(\log^2 n)$. Memory consumption would be $O(n \log n)$.
  3. The previous solution can be further optimized by adding some precalculations which will exploit the static nature of the tree so that single query becomes $O(\log n)$.
  4. You can use sweep line algorithm and a 1D segment tree to answer all queries in $O((n + m) log (n + m))$. This solution is probably the simplest to implement after summed area table.
| cite | improve this answer | |
  • $\begingroup$ Can you please explain how to do 4th? $\endgroup$ – nequit Jun 8 '17 at 20:12
  • $\begingroup$ @nequit Looks like it's described here $\endgroup$ – yeputons Jun 8 '17 at 20:13
  • $\begingroup$ @nequit You have to put some effort yourself. We won't do your homework for you. $\endgroup$ – Yuval Filmus Jun 8 '17 at 20:28
  • $\begingroup$ Sorry I read that wrong, should sleep now. Thanks yeputons. $\endgroup$ – nequit Jun 8 '17 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.