Range query (data structures)

In data structures, a range query consists of preprocessing some input data into a data structure to efficiently answer any number of queries on any subset of the input. Particularly, there is a group of problems that have been extensively studied where the input is an array of unsorted numbers and a query consists of computing some function, such as the minimum, on a specific range of the array.A range query q f ( A , i , j ) {displaystyle q_{f}(A,i,j)}   on an array A = [ a 1 , a 2 , . . , a n ] {displaystyle A=}   of n elements of some set S, denoted A [ 1 , n ] {displaystyle A}  , takes two indices 1 ≤ i ≤ j ≤ n {displaystyle 1leq ileq jleq n}  , a function f defined over arrays of elements of S and outputs f ( A [ i , j ] ) = f ( a i , … , a j ) {displaystyle f(A)=f(a_{i},ldots ,a_{j})}  .When the function of interest in a range query is a semigroup operator, the notion of f − 1 {displaystyle f^{-1}}   is not always defined, so the strategy in the previous section does not work. Andrew Yao showed that there exists an efficient solution for range queries that involve semigroup operators. He proved that for any constant c, a preprocessing of time and space θ ( c ⋅ n ) {displaystyle heta (ccdot n)}   allows to answer range queries on lists where f is a semigroup operator in θ ( α c ( n ) ) {displaystyle heta (alpha _{c}(n))}   time, where α k {displaystyle alpha _{k}}   is a certain functional inverse of the Ackermann function.All the problems described above have been studied for higher dimensions as well as their dynamic versions. On the other hand, range queries might be extended to other data structures like trees, such as the level ancestor problem. A similar family of problems are orthogonal range queries, also known as counting queries.