Design a static data structure (which does not support insertions and deletions) that stores a two-dimensional set

Question:

Design a static data structure (which does not support insertions and deletions) that stores a two-dimensional set S of n points and can answer, in O(log2 n) time, queries of the form countAllInRange(a, b, c, d), which return the number of points in S with x-coordinates in the range [a, b] and y-coordinates in the range [c, d]. What is the space used by this structure?

Fantastic news! We've Found the answer you've been seeking!