Wavelet trees are widely used in the representation of sequences, permutations, text
collections, binary relations, discrete points, and other succinct data structures. We show …

We give an-time algorithm for counting the number of inversions in a permutation on n
elements. This improves a long-standing previous bound of O (n lg n/lg lg n) that followed …

We show how to use a balanced wavelet tree as a data structure that stores a list of numbers
and supports efficient range quantile queries. A range quantile query takes a rank and the …

Range selection is the problem of preprocessing an input array A of n unique integers, such
that given a query (i, j, k), one can report the k'th smallest integer in the subarray A [i], A [i+ …

We consider the following problem: Given an unsorted array of n elements, and a sequence
of intervals in the array, compute the median in each of the subarrays defined by the …

A mode of a multiset S is an element a∈ S of maximum multiplicity; that is, a occurs at least
as frequently as any other element in S. Given an array A 1: n of n elements, we consider a …

We present three new results on one of the most basic problems in geometric data
structures, 2-D orthogonal range counting. All the results are in the w-bit word RAM model …

In this paper we design data structures supporting range median queries, ie report the
median element in a sub-range of an array. We consider static and dynamic data structures …

A mode of a multiset S is an element a in S of maximum multiplicity; that is, a occurs at least
as frequently as any other element in S. Given an array A [1: n] of n elements, we consider a …

We present O (n) O (n)-space data structures to support various range frequency queries on
a given array A 0: n-1 A 0: n-1 or tree TT with nn nodes. Given a query consisting of an …