# Orthogonal range reporting with fixed upper rectangular corner

Consider the following special case of orthogonal range searching:

Given a set $$S$$ of $$n$$ points in $$d$$ dimensions, and rectangular queries with a fixed "upper-left" rectangle corner $$(0,0,...0)$$, report the total number of points inside the rectangle.

This is different in that all rectangles queried have a fixed corner. In this case, will we have a dynamic algorithm with a better runtime, or is the problem still as hard as general orthogonal range searching?

The count of any rectangle $$C(U, L, D, R)$$ can be obtained combining the counts of 4 fixed "upper-left" retangles:

$$C(U, L, D, R) = C(0, 0, D, R) - C(0, 0, U, R) - C(U, 0, D, L) + C(0, 0, U, L)$$,

noting $$C(up, left, down, right)$$ the count in the rectangle delimited by $$(up, left, down, right)$$.

Thus, you cannot expect more than a factor 4 runtime improvement.