Find sum of values of points in 2D plane

Question

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.

Answer 1

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.