Hubbry Logo
Range treeRange treeMain
Open search
Range tree
Community hub
Range tree
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Range tree
Range tree
Range tree
View on Wikipedia
from Wikipedia
Range tree
Typetree
Invented1979
Invented byJon Louis Bentley
Time complexity in big O notation
Operation Average Worst case
Search
Space complexity
Space

In computer science, a range tree is an ordered tree data structure to hold a list of points. It allows all points within a given range to be reported efficiently, and is typically used in two or higher dimensions. Range trees were introduced by Jon Louis Bentley in 1979.[1] Similar data structures were discovered independently by Lueker,[2] Lee and Wong,[3] and Willard.[4] The range tree is an alternative to the k-d tree. Compared to k-d trees, range trees offer faster query times of (in Big O notation) but worse storage of , where n is the number of points stored in the tree, d is the dimension of each point and k is the number of points reported by a given query.

In 1990, Bernard Chazelle improved this to query time and space complexity .[5][6]

Data structure

[edit]
An example of a 1-dimensional range tree.
An example of a 1-dimensional range tree. Each node which is not a leaf stores the largest value of its left subtree.

A range tree on a set of 1-dimensional points is a balanced binary search tree on those points. The points stored in the tree are stored in the leaves of the tree; each internal node stores the largest value of its left subtree. A range tree on a set of points in d-dimensions is a recursively defined multi-level binary search tree. Each level of the data structure is a binary search tree on one of the d-dimensions. The first level is a binary search tree on the first of the d-coordinates. Each vertex v of this tree contains an associated structure that is a (d−1)-dimensional range tree on the last (d−1)-coordinates of the points stored in the subtree of v.

Operations

[edit]

Construction

[edit]

A 1-dimensional range tree on a set of n points is a binary search tree, which can be constructed in time. Range trees in higher dimensions are constructed recursively by constructing a balanced binary search tree on the first coordinate of the points, and then, for each vertex v in this tree, constructing a (d−1)-dimensional range tree on the points contained in the subtree of v. Constructing a range tree this way would require time.

This construction time can be improved for 2-dimensional range trees to .[7] Let S be a set of n 2-dimensional points. If S contains only one point, return a leaf containing that point. Otherwise, construct the associated structure of S, a 1-dimensional range tree on the y-coordinates of the points in S. Let xm be the median x-coordinate of the points. Let SL be the set of points with x-coordinate less than or equal to xm and let SR be the set of points with x-coordinate greater than xm. Recursively construct vL, a 2-dimensional range tree on SL, and vR, a 2-dimensional range tree on SR. Create a vertex v with left-child vL and right-child vR. If we sort the points by their y-coordinates at the start of the algorithm, and maintain this ordering when splitting the points by their x-coordinate, we can construct the associated structures of each subtree in linear time. This reduces the time to construct a 2-dimensional range tree to , and also reduces the time to construct a d-dimensional range tree to .

Range queries

[edit]
A 1-dimensional range query.
A 1-dimensional range query [x1, x2]. Points stored in the subtrees shaded in gray will be reported. find(x1) and find(x2) will be reported if they are inside the query interval.

A range query on a range tree reports the set of points that lie inside a given interval. To report the points that lie in the interval [x1, x2], we start by searching for x1 and x2. At some vertex in the tree, the search paths to x1 and x2 will diverge. Let vsplit be the last vertex that these two search paths have in common. For every vertex v in the search path from vsplit to x1, if the value stored at v is greater than x1, report every point in the right-subtree of v. If v is a leaf, report the value stored at v if it is inside the query interval. Similarly, reporting all of the points stored in the left-subtrees of the vertices with values less than x2 along the search path from vsplit to x2, and report the leaf of this path if it lies within the query interval.

Since the range tree is a balanced binary tree, the search paths to x1 and x2 have length . Reporting all of the points stored in the subtree of a vertex can be done in linear time using any tree traversal algorithm. It follows that the time to perform a range query is , where k is the number of points in the query interval.

Range queries in d-dimensions are similar. Instead of reporting all of the points stored in the subtrees of the search paths, perform a (d−1)-dimensional range query on the associated structure of each subtree. Eventually, a 1-dimensional range query will be performed and the correct points will be reported. Since a d-dimensional query consists of (d−1)-dimensional range queries, it follows that the time required to perform a d-dimensional range query is , where k is the number of points in the query interval. This can be reduced to using a variant of fractional cascading.[2][4][7]

See also

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Range tree

View on Grokipedia
from Grokipedia
A range tree is a multidimensional in designed for efficient orthogonal , enabling the storage of a set of points in k-dimensional space and the retrieval of all points lying within a specified axis-aligned query region. Introduced by Jon Louis Bentley in 1979, it builds upon binary search trees to handle range queries with optimal worst-case performance in theoretical analyses, though at the cost of higher space usage compared to simpler structures like k-d trees. In its basic 2D form, a range tree consists of a primary balanced organized by x-coordinates, where each node stores an auxiliary balanced (or sorted ) on the y-coordinates of the points in its subtree, allowing queries to decompose into O(log n) canonical subtrees for efficient secondary searches. This layered structure generalizes recursively to higher dimensions, with each level using a (k-1)-dimensional range tree as the auxiliary structure. Preprocessing a set of n points requires O(n log n) time in 2D and O(n logk-1 n) in k dimensions, while space consumption is O(n log n) for 2D and O(n logk-1 n) overall due to the nested trees. Queries in a d-dimensional range tree achieve O(logd n + k) time for reporting k points or O(logd n) for counting, making it suitable for applications in databases, geographic information systems, and statistical analysis where multidimensional range reporting is frequent, despite practical trade-offs in storage for higher dimensions. Later refinements, such as , can reduce query times to O(log n + k) in 2D by linking auxiliary structures, though at additional preprocessing cost.

Overview

Definition and purpose

A range tree is a multi-level tree data structure for storing a set of points in k-dimensional space, enabling efficient orthogonal range queries. It consists of a primary balanced binary search tree organized by the first coordinate (e.g., x), where each node contains a secondary balanced binary search tree on the second coordinate for the points in its subtree, with this nesting continuing for higher dimensions up to k. This augmentation allows the structure to report points within axis-aligned hyperrectangles, such as those defined by intervals on each coordinate axis. The purpose of a range tree is to support fast retrieval of points satisfying orthogonal range queries, including counting the number of points in a range, reporting all such points, or computing aggregates like sums over them. Orthogonal range queries seek all points p = (p_1, ..., p_k) where a_i ≤ p_i ≤ b_i for given intervals [a_i, b_i] on each dimension i; naive approaches, such as linearly scanning the entire set of n points, require O(n) time per query, which becomes prohibitive for large datasets in applications like geographic information systems or database indexing. Range trees address this by preprocessing the points into a hierarchical structure that prunes irrelevant subtrees during queries, achieving O(\log^k n + m) time complexity, where m is the number of points reported (or 0 for counting queries). For example, in a 2D range tree storing points like (1,4), (2,6), (3,2), (5,5), and (7,3), a query for points with x in [2,5] and y in [3,6] would traverse the primary x-tree to identify the subtrees covering [2,5], then query the associated y-trees in those nodes for the y-interval [3,6], reporting points (2,6) and (5,5). This structure is particularly valuable in for handling dynamic or static point sets where frequent multidimensional range searches are needed.

Historical development

The concept of the range tree emerged in the late 1970s as part of early efforts in to efficiently handle orthogonal range queries on point sets. In 1978, George S. Lueker introduced a foundational for two-dimensional orthogonal range queries, employing a tree-of-trees approach that layered binary search trees to decompose and search multidimensional spaces, achieving query times of O(log⁡2n+k)O(\log^2 n + k) for nn points and kk reported outputs. This work laid the groundwork for multidimensional extensions by addressing the challenges of reporting points within axis-aligned rectangles. Building on related structures like the , introduced by Louis Bentley in 1975 for nearest-neighbor searches, and the , developed by in 1977 for interval management in one-dimensional problems, Lueker's structure marked an initial shift toward specialized tools for geometric . In 1979, Bentley and Jerome H. Friedman formalized the in their survey on data structures for , presenting it explicitly for one-dimensional range queries on static point sets with balanced binary search trees that support searches in O(log⁡n+k)O(\log n + k) time. This one-dimensional variant emphasized preprocessing for efficient queries, influencing subsequent geometric applications. Bentley refined the multidimensional version in 1980, integrating it into a divide-and-conquer framework for problems like closest-pair finding and range reporting, where a primary tree on one coordinate is augmented with secondary trees on others, yielding O(log⁡dn+k)O(\log^d n + k) query times for dd dimensions. These early developments focused on static datasets, drawing from the growing field of , which had gained momentum through works on convex hulls and Voronoi diagrams in the mid-1970s. During the 1980s, range trees saw widespread adoption for static geometric queries in algorithms for map overlay, visibility, and spatial databases, as documented in surveys and implementations within the emerging discipline. Optimizations like , introduced by and Leo J. Guibas in 1986, enhanced range trees by linking sorted lists across tree levels with auxiliary pointers, reducing query times to O(log⁡n+k)O(\log n + k) in two dimensions through shared search paths. Dynamic variants, supporting insertions and deletions while maintaining balanced structures, were developed in the 1980s, with Mark H. Overmars extending partial rebuilding techniques to achieve polylogarithmic update times for multidimensional cases. This evolution reflected the shift toward fully dynamic data structures amid increasing demands for real-time .

Structure

One-dimensional range tree

A one-dimensional range tree is a balanced , such as an or red-black tree, constructed on a set of n sorted keys representing one-dimensional points, typically the x-coordinates. The tree is built by recursively selecting the key as the root, with the left subtree containing all keys less than or equal to the root and the right subtree containing all larger keys. To support efficient range reporting, each node stores a sorted list of all keys in its subtree, obtained by merging the sorted lists from its children during construction. The of a one-dimensional range tree is O(n log n), as each key appears in the sorted lists of O(log n) nodes corresponding to the path from the root to its position. A range query for points in [low, high] begins by finding the nodes where the query range splits the tree, using two standard binary searches to identify O(log n) disjoint subtrees that exactly cover the desired interval. For each node, the associated sorted list is scanned for keys within [low, high], with binary search locating the start and end indices in O(log n) time per list before reporting the intervening elements in O(k) time, where k is the number of reported points. For example, given a sorted of daily sales figures, a one-dimensional enables querying the count or sum of sales in a time interval [low, high] by reporting the relevant values from the subtrees and aggregating them as needed. This structure forms the basis for extensions to higher dimensions using nested trees.

Multidimensional extensions

To generalize the one-dimensional to higher dimensions, the structure is extended recursively to handle orthogonal range queries on points in kk-dimensional . A kk-dimensional consists of a primary balanced binary search tree (BST) organized by the first coordinate (e.g., x1x_1); each node in this primary tree stores an associated (k−1)(k-1)-dimensional containing the points from its subtree, sorted by the remaining coordinates. This nesting allows efficient decomposition of multidimensional queries by isolating relevant subsets at each level. The recursion terminates at the base case of a 1D range tree. For the two-dimensional case (k=2k=2), the outer BST is built on the xx-coordinates of the points, and each node contains an inner 1D range tree (or sorted structure equivalent to a BST) on the yy-coordinates of the points in its canonical subset. This hierarchical organization replicates points across multiple subtrees to facilitate range searching without full traversal. The total space complexity arises from this replication: each of the nn points appears in O(log⁡n)O(\log n) nodes per dimension due to the tree height, leading to O(nlog⁡k−1n)O(n \log^{k-1} n) space overall for kk dimensions. For instance, in 2D, each point is stored in O(log⁡n)O(\log n) inner trees, yielding O(nlog⁡n)O(n \log n) space. In a 2D example with points (x,y)(x, y), a rectangular query [xmin⁡,xmax⁡]×[ymin⁡,ymax⁡][x_{\min}, x_{\max}] \times [y_{\min}, y_{\max}] involves traversing the outer xx-tree to identify O(log⁡n)O(\log n) canonical nodes whose subtrees intersect the xx-range, then querying the inner yy-trees at those nodes for the yy-range. This approach leverages the nested structure to report all points within the rectangle efficiently.

Operations

Construction and building

Range trees are typically constructed in a static setting, where the initial set of nn points in kk-dimensional space is fixed and provided upfront, allowing for efficient preprocessing without support for immediate updates. The standard algorithm employs a top-down recursive approach, beginning with the construction of a primary balanced binary search tree (BST) on the first coordinate (e.g., xx). The points are sorted by this coordinate, and the tree is built by selecting the median as the root's splitting value, recursively partitioning the left and right subsets, and continuing until single points or small sets remain. At each node of this primary tree, an associated secondary structure—a (k−1)(k-1)-dimensional range tree—is built on the canonical subset of points in the subtree, sorted by the next coordinate (e.g., yy), with this process nesting recursively for higher dimensions. This recursive construction ensures balance, assuming the input points can be presorted by each dimension to avoid redundant sorting costs during . An alternative bottom-up method can be used if points are presorted once per dimension: start from (individual points) and merge upward, attaching sorted sublists at each level to form the associated trees, which linearizes the merging step after initial sorting. Both approaches focus on static initial loading, with presorting enabling O(nlog⁡n)O(n \log n) time per dimension upfront. The construction process inherently dominates the space usage, as each level of the primary tree requires storing a full sorted list of the subtree's points for the associated secondary tree, leading to an overall of O(nlog⁡k−1n)O(n \log^{k-1} n). The for building a kk-dimensional range tree is O(nlog⁡k−1n)O(n \log^{k-1} n), achieved through the and sorting/merging at each nesting level; for the base case of k=2k=2, this simplifies to O(nlog⁡n)O(n \log n). Below is an outline of for the 2D case, generalizable to higher dimensions by replacing the secondary structure with a recursive call to build a (k−1)(k-1)-D tree:

BUILD_2D_RANGE_TREE(P): if |P| == 0: return NULL if |P| == 1: create leaf node v with point p in P return v // Assume P presorted by x; find median split x_mid = median x-coordinate of P P_left = points in P with x <= x_mid P_right = points in P with x > x_mid // Recurse v_left = BUILD_2D_RANGE_TREE(P_left) v_right = BUILD_2D_RANGE_TREE(P_right) // Build associated y-tree on all points in P (presorted by y) T_y = BUILD_BST(P sorted by y) // Create root node v = new node with x_mid, v_left, v_right, T_y return v

BUILD_2D_RANGE_TREE(P): if |P| == 0: return NULL if |P| == 1: create leaf node v with point p in P return v // Assume P presorted by x; find median split x_mid = median x-coordinate of P P_left = points in P with x <= x_mid P_right = points in P with x > x_mid // Recurse v_left = BUILD_2D_RANGE_TREE(P_left) v_right = BUILD_2D_RANGE_TREE(P_right) // Build associated y-tree on all points in P (presorted by y) T_y = BUILD_BST(P sorted by y) // Create root node v = new node with x_mid, v_left, v_right, T_y return v

This pseudocode highlights the recursive nature and attachment of subtrees, with presorting ensuring efficiency.

Range querying

Range trees support orthogonal range queries in kk-dimensional space, where the query range is defined by a kk-dimensional axis-aligned . The primary query types include reporting, which retrieves all points within the range; , which determines the number of points in the range; and semigroup queries, which compute an associative operation (such as or minimum) over the values associated with points in the range. For reporting and counting queries, the algorithm exploits the hierarchical structure of the range tree without requiring node augmentation, while semigroup queries necessitate augmenting nodes with precomputed aggregates (e.g., subtree sums or minima) to enable efficient combination during traversal. The general procedure for a kk-dimensional query begins by traversing the primary tree, sorted on the first coordinate, to identify O(log⁡n)O(\log n) disjoint canonical subtrees whose points lie entirely within the query hyperrectangle along the first dimension. For each such canonical subtree, the associated secondary structure—a (k−1)(k-1)-dimensional range tree on the remaining coordinates—is queried recursively with the corresponding subrange. This decomposition ensures that the query range is fully covered without redundant searches. In the two-dimensional case, the primary tree is a balanced on the x-coordinates, with each node storing a secondary (or sorted array) on the y-coordinates of points in its subtree. To process a query [x1,x2]×[y1,y2][x_1, x_2] \times [y_1, y_2], the algorithm first searches the primary tree to find the O(log⁡n)O(\log n) nodes whose subtrees span the x-interval exactly (the canonical nodes along the paths from the roots to the splitting nodes for x1x_1 and x2x_2). For each of these nodes, a one-dimensional range query is performed on the associated y-structure to report or points within [y1,y2][y_1, y_2]. This step visits O(log⁡n)O(\log n) secondary trees, each searchable in O(log⁡n)O(\log n) time. The query time is output-sensitive for reporting, achieving O(log⁡kn+∣output∣)O(\log^k n + |\text{output}|) in kk dimensions, where ∣output∣|\text{output}| is the number of points reported; counting and queries take O(log⁡kn)O(\log^k n) time, independent of output size, due to the use of augmented aggregates that allow constant-time combinations at internal nodes. This complexity arises recursively, satisfying the relation Q(k,n)=O(log⁡n⋅Q(k−1,n))Q(k,n) = O(\log n \cdot Q(k-1,n)) with base case Q(1,n)=O(log⁡n+∣output∣)Q(1,n) = O(\log n + |\text{output}|) for the one-dimensional query. As an illustrative example, consider reporting all points within a 2D bounding box [x1,x2]×[y1,y2][x_1, x_2] \times [y_1, y_2] in a set of nn points. The primary x-tree traversal identifies nodes covering the x-range, such as the right subtrees along the path to x1x_1 and left subtrees along the path to x2x_2, plus the subtrees of the if applicable. Each of these O(log⁡n)O(\log n) y-trees is then searched to output points with y-coordinates in [y1,y2][y_1, y_2], yielding the full set in O(log⁡2n+k)O(\log^2 n + k) time, where kk is the output size.

Insertion and deletion

Insertion of a point into a begins by traversing the primary balanced (BST) to the appropriate insertion point based on the point's coordinate in the primary , similar to standard BST insertion. At each node along this O(log n) path, the point is also inserted into the associated secondary tree (for 2D) or the nested range tree structure (for higher dimensions), ensuring the auxiliary structures remain sorted by the subsequent coordinates. If the primary tree employs self-balancing mechanisms like AVL trees, local rotations are applied as needed to restore balance, which recursively updates the associated subtrees at affected nodes. Deletion follows a comparable traversal: the point is located in the primary tree, removed from the leaf, and then deleted from the associated subtrees of all ancestors along the path. Underflow conditions in the primary tree trigger rebalancing operations, such as rotations, to maintain height balance, with corresponding adjustments to the nested structures. These operations ensure the integrity of the multidimensional ordering without disrupting query efficiency. For a kk-dimensional range tree using balanced variants, both insertion and deletion achieve O(log⁡kn)O(\log^k n) amortized time complexity per operation, where nn is the number of points, as each of the kk levels requires O(log⁡n)O(\log n) work for traversal and updates. A key challenge in these operations is preserving balance and sorted order across the nested structures, as imbalances at one level can propagate and affect auxiliary trees, requiring careful recursive handling during rebalancing. To address this, simpler amortized balancing schemes like scapegoat trees or treaps can replace stricter methods such as AVL trees in the underlying BSTs, reducing implementation complexity while maintaining the overall logarithmic bounds. Dynamic range trees were refined in the 1990s through advancements in dynamic techniques, enabling O(log⁡kn)O(\log^k n) updates without full rebuilds after each insertion or deletion.

Advanced topics

Efficiency optimizations

One key efficiency optimization for range trees is , a technique that connects the secondary search structures across levels to eliminate redundant binary searches for the same key. Introduced by Chazelle and Guibas in , this method applies to the nested trees in multidimensional range trees by maintaining sorted lists with pointers that allow traversal in constant time per step after the initial search. In two dimensions, it reduces the orthogonal range query time from O(log⁡2n+k)O(\log^2 n + k) to O(log⁡n+k)O(\log n + k), where nn is the number of points and kk is the output size, by cascading paths through the associated structures. This optimization incurs a space trade-off, increasing the storage from O(nlog⁡n)O(n \log n) to O(nlog⁡n)O(n \log n) in practice due to the additional pointers, but the time savings justify it for query-intensive applications. For higher dimensions, layered range trees—range trees enhanced with —extend this benefit, achieving query times of O(log⁡d−1n+k)O(\log^{d-1} n + k) for dd-dimensional orthogonal range reporting while using O(nlog⁡d−1n)O(n \log^{d-1} n) space. These layered structures replace full secondary trees with sorted arrays linked by forward pointers, further streamlining searches in nested levels. Persistent versions of range trees support versioning by incorporating persistent binary search trees, allowing updates to create new versions without modifying prior ones, which is useful for maintaining historical snapshots in dynamic environments. This preserves query efficiency across versions at the cost of additional space proportional to the number of updates. For higher-dimensional cases, advanced layered range trees can further optimize query times to O(log⁡n⋅(log⁡log⁡n)d−2+k)O(\log n \cdot (\log \log n)^{d-2} + k) through refined pointer networks and techniques.

Variants and generalizations

Priority search trees represent a variant of range trees augmented with priority queues to handle specialized queries involving nearest neighbors or top-k elements within a range. Introduced by McCreight, these structures combine a on one coordinate with a heap-like organization on priorities in the other dimension, enabling three-sided orthogonal range queries that report points in priority order. They achieve O(log n + k) query time for reporting k points using O(n) space, making them suitable for semi-dynamic settings where insertions and deletions are supported efficiently. Segment trees serve as a flat alternative to range trees, particularly for interval data rather than point sets, by partitioning the universe into canonical segments and storing aggregated information at nodes. Unlike range trees, which organize points in a tree of trees for multidimensional orthogonal queries, segment trees focus on stabbing queries (e.g., finding all intervals containing a point) with O(log n + k) time and O(n) space in one dimension, extending to higher dimensions via layered structures. This makes them preferable for problems involving dynamic updates on linear arrays or intervals, though they lack the nested tree depth of range trees for pure point-based multidimensional searches. Higher-dimensional range trees generalize the two-dimensional structure by nesting auxiliary trees recursively, supporting d-dimensional orthogonal range queries in O(log^d n + k) time for reporting k points, with O(n log^{d-1} n) space for constant d. For 3D orthogonal queries, this yields O(log^3 n + k) reporting time. Generalizations to non-orthogonal ranges, such as halfspaces or disks, often employ transformations that map the problem to higher-dimensional orthogonal queries solvable by range trees. For instance, linearization techniques convert semialgebraic ranges (e.g., circular queries in 2D) into halfspace searches in one higher dimension, preserving logarithmic query times at the cost of increased dimensionality. Integration with R-trees for spatial data creates hybrid structures, where range trees handle precise point queries within R-tree bounding boxes, improving secondary-memory performance for large-scale geographic datasets with O(log_B n + k) I/O complexity in 2D. Range trees excel in exact orthogonal queries due to their balanced nesting, but perform less efficiently for approximate or circular ranges without transformations, as their axis-aligned structure incurs higher space and time overheads compared to specialized spatial indexes like R-trees for non-orthogonal shapes.

Applications and comparisons

Practical uses

Range trees find extensive application in , particularly within geographic information systems (GIS) for performing spatial queries on point data. For instance, they enable efficient retrieval of all points lying within a specified rectangular on a , such as identifying all landmarks within a bounded area for or systems. This orthogonal capability supports real-time in GIS software, where datasets can include millions of coordinates representing features like roads, buildings, or natural resources. In database systems, range trees serve as an indexing mechanism for multi-attribute range queries in relational databases, allowing the selection of records satisfying multiple range conditions simultaneously. A representative example is querying employee records where age falls within [20, 40] and salary within [$50,000, $100,000], which demonstrates their utility in handling orthogonal range searches over multidimensional data like demographic or financial attributes. While practical implementations often adapt range trees in custom extensions or research prototypes for spatial extensions of systems like , they provide logarithmic query times essential for large-scale data retrieval without full table scans. Beyond these domains, range trees are employed in computer graphics for ray-shooting queries, which facilitate ray tracing and hidden-surface removal by reporting the first intersecting object along a ray path, aiding in rendering complex scenes with efficient intersection detection. In bioinformatics, augmented range trees support genomic interval queries, such as identifying overlapping DNA sequences or regulatory elements within specified chromosomal ranges, enabling scalable analysis of large-scale genomic datasets. Software libraries provide robust implementations of range trees for practical development. The in C++ includes d-dimensional range tree classes that support and range querying operations, though the trees are static and do not support insertions or deletions after , making them accessible for integrating into GIS, graphics, or bioinformatics applications.

Comparison to alternatives

Range trees offer guaranteed logarithmic query times for orthogonal range searches in fixed dimensions but at the cost of higher space usage compared to kd-trees. Specifically, a d-dimensional range tree requires O(nlog⁡d−1n)O(n \log^{d-1} n) space and supports range reporting queries in O(log⁡dn+k)O(\log^d n + k) time, where nn is the number of points and kk is the output size, providing worst-case efficiency independent of data distribution. In contrast, kd-trees use linear O(n)O(n) space and achieve O(n1−1/d+k)O(n^{1-1/d} + k) query time on average, making them simpler and more space-efficient for low-dimensional data, though their worst-case performance can degrade to O(n)O(n) due to unbalanced partitions in adversarial inputs. Kd-trees are thus preferred for nearest-neighbor searches and approximate queries in practical spatial applications where exact bounds are less critical, while range trees excel in scenarios demanding predictable performance, such as offline geometric computations. Compared to R-trees, range trees are optimized for exact point queries in static, fixed-dimensional spaces but lack support for dynamic updates and approximate spatial extents. R-trees, designed for indexing multi-dimensional rectangles or points in secondary storage, maintain O(n)O(n) space and deliver average-case O(n1−1/d+k)O(n^{1-1/d} + k) query times, with built-in handling for insertions and deletions through node splitting and merging. This makes R-trees more suitable for dynamic environments like geographic information systems (GIS) and database spatial indexing, where data evolves and queries may involve overlapping bounding boxes; however, their performance suffers from overlap in high dimensions, leading to more traversed nodes than range trees' structured searches. Range trees, being static and point-focused, avoid such overlaps but require rebuilding for updates, limiting their use in real-time applications. Interval trees and segment trees serve primarily one-dimensional range queries on intervals or array segments, differing from range trees' focus on multi-dimensional points. An interval tree stores intervals in O(n)O(n) space and answers stabbing queries (finding all intervals containing a point) or overlap queries in O(log⁡n+k)O(\log n + k) time, ideal for tasks like scheduling or genomic overlap detection. Segment trees, similarly using O(n)O(n) space, support range aggregate queries (e.g., sum or min) on arrays in O(log⁡n)O(\log n) time with updates, but they are inherently 1D and less adaptable to higher dimensions without extensions that increase complexity. Range trees generalize these to d dimensions for point-in-range reporting but trade off with exponential space growth in dd, whereas 1D structures like interval or segment trees remain linear and efficient for linear data. For even simpler 1D prefix sum queries, Fenwick trees (binary indexed trees) offer O(n)O(n) space and O(log⁡n)O(\log n) time for updates and queries, providing a lightweight alternative to segment trees when only cumulative operations are needed, though without the full flexibility for arbitrary range aggregates. A key limitation of range trees is their space consumption, which scales as O(nlog⁡d−1n)O(n \log^{d-1} n) and becomes prohibitive for high dd (e.g., beyond 3-4 dimensions), rendering them impractical for very high-dimensional data where alternatives like or are favored. In such cases, 1D structures like Fenwick trees suffice for prefix computations without multi-dimensional overhead.
Data StructureSpace ComplexityQuery Time (Reporting)DimensionsKey Use Cases
Range TreesO(nlog⁡d−1n)O(n \log^{d-1} n)O(log⁡dn+k)O(\log^d n + k)Multi-DExact orthogonal point queries
kd-TreesO(n)O(n)O(n1−1/d+k)O(n^{1-1/d} + k)Multi-DSpatial partitioning, NN search
R-TreesO(n)O(n)O(n1−1/d+k)O(n^{1-1/d} + k)Multi-DDynamic spatial indexing
Interval TreesO(n)O(n)O(log⁡n+k)O(\log n + k)1DInterval overlap/stabbing
Segment TreesO(n)O(n)O(log⁡n+k)O(\log n + k)1DArray range aggregates
Fenwick TreesO(n)O(n)O(log⁡n)O(\log n)1DPrefix sums/updates

References

  1. https://apps.dtic.mil/sti/tr/pdf/ADA060584.pdf
  2. https://dl.acm.org/doi/10.1145/356789.356797
  3. https://www.cs.umd.edu/class/fall2020/cmsc420-0201/Lects/lect17-range-tree.pdf
  4. https://jeffe.cs.illinois.edu/teaching/225H/notes/range-segment.pdf
  5. https://people.csail.mit.edu/radu/6854proj.pdf
  6. https://ieeexplore.ieee.org/document/4567959
  7. https://scholar.google.com/citations?view_op=view_citation&hl=en&user=AFHvuhMAAAAJ&citation_for_view=AFHvuhMAAAAJ:u5HHmVD_uO8C
  8. https://dl.acm.org/doi/10.1145/358841.358850
  9. http://graphics.stanford.edu/courses/cs428-03-spring/Papers/readings/DataBases/matousek_range_search_ComputingSurvey94.pdf
  10. https://www.cs.princeton.edu/~chazelle/pubs/FractionalCascading1.pdf
  11. https://books.google.com/books/about/The_Design_of_Dynamic_Data_Structures.html?id=Z8R9zaUQ6xAC
  12. https://www.cs.cmu.edu/afs/cs/academic/class/15456-s14/Handouts/BKOS.pdf
  13. https://cs.brown.edu/courses/cs252/misc/slides/orthsearch.pdf
  14. https://dspace.mit.edu/bitstream/handle/1721.1/90370/6-851-spring-2010/contents/lecture-notes/MIT6_851S10_lec04.pdf
  15. https://people.csail.mit.edu/rivest/pubs/GR93.pdf
  16. https://link.springer.com/article/10.1007/BF01840440
  17. https://www.cs.princeton.edu/~chazelle/pubs/FractionalCascading2.pdf
  18. https://www.cs.umd.edu/class/fall2021/cmsc754/Lects/lect15-orth-range-tree.pdf
  19. https://www.cs.umd.edu/class/spring2022/cmsc420-0101/Lects/lect16-range-tree.pdf
  20. https://www.csun.edu/~ctoth/Handbook/chap40.pdf
  21. https://dl.acm.org/doi/abs/10.1137/0214021
  22. https://cp-algorithms.com/data_structures/segment_tree.html
  23. https://research.cs.queensu.ca/home/yurai/Publications/2008-546.pdf
  24. https://users.cs.duke.edu/~pankaj/publications/surveys/holyoke-survey.pdf
  25. https://www.nature.com/articles/s41598-019-41451-3
  26. https://doc.cgal.org/latest/SearchStructures/index.html
  27. https://tildesites.bowdoin.edu/~ltoma/teaching/cs3250-CompGeom/spring16/Lectures/cg-rangetrees.pdf
  28. https://dl.acm.org/doi/10.1145/361002.361007
  29. https://dl.acm.org/doi/10.1145/971697.602266
  30. https://pub.ista.ac.at/~edels/Papers/1981-01-IntersectingOrthogonalObjects.pdf
  31. https://www.baeldung.com/cs/tree-segment-interval-range-binary-indexed
  32. https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.4380240306
Add your contribution
Related Hubs
User Avatar
No comments yet.