Range Minimum Query
Encyclopedia
Given an array
of 
ordered objects (such as numbers), a Range Minimum Query (or RMQ) from 
to 
asks for the position of a minimum element in the sub-array 
.
For example, when
, then the range minimum query for the range from 3 to 8 returns 1, as 
is the minimum in the sub-array 
.
In a typical setting, the array
is static, i.e., elements are not inserted or deleted during a series of queries, and the queries to be answered on-line (i.e., the whole set of queries are not known in advance to the algorithm). In this case a suitable preprocessing the array into a data structure (often called a preprocessing scheme) ensures faster query answering.
It is known that a
-time preprocessing is sufficient to answer subsequent queries in 
time. The space of the resulting scheme is actually very small, namely 
bits (see ).
RMQs can be used to solve the lowest common ancestor
problem, and is used as a tool for many tasks in exact and approximate string matching.
Array
In computer science, an array data structure or simply array is a data structure consisting of a collection of elements , each identified by at least one index...
of ordered objects (such as numbers), a Range Minimum Query (or RMQ) from to asks for the position of a minimum element in the sub-array .For example, when
, then the range minimum query for the range from 3 to 8 returns 1, as is the minimum in the sub-array .In a typical setting, the array
is static, i.e., elements are not inserted or deleted during a series of queries, and the queries to be answered on-line (i.e., the whole set of queries are not known in advance to the algorithm). In this case a suitable preprocessing the array into a data structure (often called a preprocessing scheme) ensures faster query answering.It is known that a
-time preprocessing is sufficient to answer subsequent queries in time. The space of the resulting scheme is actually very small, namely bits (see ).RMQs can be used to solve the lowest common ancestor
Lowest common ancestor
The lowest common ancestor is a concept in graph theory and computer science. Let T be a rooted tree with n nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants .The LCA of v and w in T is the shared ancestor of v...
problem, and is used as a tool for many tasks in exact and approximate string matching.