A data structure for multi-dimensional range reporting
Yakov Nekrich · 2007
We present a static data structure for orthogonal range reporting on a U x U x U integer grid. Our data structure supports orthogonal range reporting queries in O((log log n)2 + log log U + k) time and uses O(n log4 n) space, where k is the size of the answer. We describe a static data structure for range reporting in R4 with O(log nlog log n +k) query time and a static data structure for range reporting in Rd, d ≥ 5, with query time O((logd-3 n)/(log log n)d-5 +k). We also describe a semi-dynamic data structure that supports range reporting queries in R3 in O(log nlog log n +k) time and insertions in polylogarithmic time.