Given data points in some space, serve queries about which points are in a subset of that space. Different data structures will handle different query shapes. Types of queries:
A range query $q$ is decomposable
if $q = x \cup y \to \text{query}(Q) = \text{query}(X) \cup \text{query}(Y)$. If the query function is closed under the union operation.
A simple version of the range query problem space.
Dynamic
property means that it supports insertion and deletion of data points.
Data have real-number keys as well as other associated values.
A range is an interval $L \leq key \leq R$.
The result of a query is a function of associate values, has a range over data keys.
This solution maintains data keys in a balanced binary search tree. Then each tree node is augmented by $\otimes$. For each node x: augment(x)= value(x) $\otimes$ augment(x.left) $\otimes$ augment(x.right)
Use the augment function to update augmented values after insertion, deletion, or rotation. For insertion and deletion, have to update everything back to the root. For rotation, only have to recompute augmented value for the new lower node.
Querying: Perform a binary search to identify nodes closest to but within the query bounds. Use the augmented values of nodes encountered during the searches in order to reconstruct the query function over the correct range. The augmented values help prevent us from requiring to traverse the entire range in question.
When $\otimes$ is $O(1)$, insertion and deletion updates are $O(\log n)$.
Retrieval is $O(\log n + k)$ for an unaugmented binary search tree which has to traverse the entire range. Retrieval in a tree augmented with range count is …
Equivalent to the Lowest Common Ancestor problem. Can be solved with linear space requirements and constant query time. What is the minimum value in a subarray? Given a a static array $A[0,\dots,n-1]$. What is $min(A[i]\dots A[j])$ for given $0 \leq i \leq j \lt n$
Make a binary tree with the elements of A at its leaves. Each internal node stores the minimum of its 2 children. O(n) space and O(log n ) time, and it allows updates.
Build a table T such that T[i,j] stores the query results for query(i,j). Takes O(n^2) space, O(1) query time.
If you take two overlapping range queries, the query of their union is the minimum of their query values. Optimize the table solution by stoing every possible range covered by 2 smaller ranges. Define an array U[i,k] = query(i,i+2^k - 1). Now U[i,0] = A[i] U[i,x] (x > 0) = min(U[i,x-1] , U[i+2^{x-1},x-1]).
Given range-minimum data: $A[0,\dots,n-1]$. Construct a Cartesian tree out of $A$. The root is the minimum of the array, then recurse for two new sub-arrays.
Equivalent to the Range Minimum problem. Given a rooted tree and two nodes (x,y), what is the closest node that is an ancestor of both of them. (each node is an ancestor of itself).
[http://en.wikipedia.org/wiki/Cartesian_tree Cartesian Tree] construction:
Distance(a,b) = distance(a,mouth) + distance(b,mouth) - 2*distance(LCA(a,b),mouth). The Lowest-Common Ancestor lookup allows for this quick distance formula.
bandwidth(x,y) = minimum edge bandwidth on path from x to y. Construct a “Cartesian tree”, a binary tree in which internal nodes correspond to edges of N, and leaves correspond to vertices. Left/right child orientation doesn't matter.
Write down the depth of each entry of an Euler tour of A into a new array A'. -Note that each adjacent pair in A' differs by at most 1.
To find LCA, find first occurrence of each node in A'. Range minimum on this range in A' provides the LCA node.
Can handle all possible range queries by combining the table of range solutions with an array of block minima.