tag

#range-query

5 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Interval Tree Search

Interval Tree Search Interval tree search finds all intervals that overlap a given query interval. It extends a binary search tree by storing interval metadata at each node to support efficient range queries. Each node represents an interval and maintains auxiliary information to guide pruning during search. Problem Given a set of intervals and a query interval $[q_l, q_r]$, find all intervals $[l, r]$ such that: $$ l \le q_r...
algorithms searching interval-tree range-query
Wiki › Algorithms › 02. Data Structures › 1. Core Data Structures and Operations › 1.1 Arrays and Dynamic Arrays ›

Prefix Sum Array

Prefix Sum Array A prefix sum array stores cumulative sums so that any range sum can be computed in constant time. You use it when many range sum queries are performed on static data. Problem Given an array $A$ of length $n$, support queries of the form: $$ \sum_{i=l}^{r} A[i] $$ where $$ 0 \le l \le r < n $$ Structure Define a prefix array $P$ such that: $$...
data-structures arrays prefix-sum range-query
Wiki › Algorithms › 02. Data Structures ›

2. Advanced Data Structures and Operations

2. Advanced data structures and operations section name 2.1 Balanced Search Trees 2.2 Range Query Structures 2.3 Fenwick Tree Variants 2.4 Segment Tree Variants 2.5 Disjoint Set Union Variants 2.6 Tries and Prefix Structures 2.7 Order Statistic Structures
algorithms data-structures trees range-query
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Equal Range

Equal Range Search Equal range search finds the contiguous range of indices where a value $x$ appears in a sorted array. It returns a pair of indices: $$ [l, r) $$ such that all elements equal to $x$ lie within this interval. This operation combines lower bound and upper bound. Problem Given a sorted array $A$ of length $n$ and a value $x$, find indices $l$ and $r$ such that:...
algorithms searching binary-search range-query
Wiki › Algorithms › 02. Data Structures › 2. Advanced Data Structures and Operations ›

2.2 Range Query Structures

2.2 Range query structures, 70 index slug name 1 range-query Range Query 2 static-range-query Static Range Query 3 dynamic-range-query Dynamic Range Query 4 range-sum-query Range Sum Query 5 range-minimum-query Range Minimum Query 6 range-maximum-query Range Maximum Query 7 range-count-query Range Count Query 8 range-frequency-query Range Frequency Query 9 range-mode-query Range Mode Query 10 range-median-query Range Median Query 11 range-majority-query Range Majority Query 12 prefix-sum-query Prefix Sum Query 13 prefix-xor-query Prefix...
algorithms data-structures range-query