# Optimal Static Range Reporting in One Dimension

Technical Report, ALCOMFT-TR-01-53, ALCOM-FT, 13 pages, May 2001.

## Abstract

We consider static one dimensional range searching problems. These
problems are to build static data structures for an integer set
*S* ⊆ *U*, where *U* = {0,1,...,2^{w}-1}, which support
various queries for integer intervals of *U*. For the query of
reporting all integers in *S* contained within a query interval, we
present an optimal data structure with linear space cost and with
query time linear in the number of integers reported. This result
holds in the unit cost RAM model with word size *w* and a standard
instruction set. We also present a linear space data structure for
approximate range counting. A range counting query for an interval
returns the number of integers in *S* contained within the interval.
For any constant ε>0, our range counting data structure
returns in constant time an approximate answer which is within a
factor of at most 1+ε of the correct answer.

**Online version**
alcomft-tr-01-53.pdf (179 Kb)

**BIBT**_{E}X entry

@techreport{alcomft-tr-01-53,
author = "Stephen Alstrup and Gerth St{\o}lting Brodal and Theis Rauhe",
institution = "ALCOM-FT",
month = "May",
number = "ALCOMFT-TR-01-53",
pages = "13",
title = "Optimal Static Range Reporting in One Dimension",
year = "2001"
}