# Find sum of values of points in 2D plane

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.

• 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. – Yuval Filmus Jun 8 '17 at 16:15
• I don't know how to solve it in sublinear time. – nequit Jun 8 '17 at 16:22
• Try to use k-d trees or a similar data structure. – Yuval Filmus Jun 8 '17 at 16:24
• How, can you provide any useful link? – nequit Jun 8 '17 at 16:31
• 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. – Yuval Filmus Jun 8 '17 at 16:32

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.