Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Two-dimensional range trees: count a static rectangle

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A two-dimensional range tree organizes a static point set by x in a balanced binary tree. Every node also stores the y coordinates of all points in its subtree in sorted order. When a query rectangle fully covers a node's x range, two binary searches in its y list count points in the half-open y interval without descending to individual leaves. A partially covered x node descends to children; a disjoint node contributes zero. This implementation counts points but does not report their IDs. Duplicate x or y coordinates are permitted and counted individually, while duplicate depot IDs are rejected. The query uses [xLow,xHigh) and [yLow,yHigh), including the lower edges and excluding the upper edges.

Operational case

Five facilities include pump-47 at (47,52), valve-19 at (19,61), sensor-61 at (52,58), grid-83 at (180,70), and bay-29 at (47,64). The window x from 15 to 60 and y from 45 to 65 counts four facilities. A narrow window x from 47 to 48 and y from 60 to 65 counts only bay-29. The two points at x=47 stay distinct in every sorted y list. If a facility moves, updating only its leaf leaves stale y arrays along the ancestor path; this static implementation must rebuild from a new snapshot. The same half-open edge rule must be used by both the oracle and the index.

Working Python program

python
from bisect import bisect_left


class RangeNode:
    def __init__(self, points):
        self.low_x = points[0][0]
        self.high_x = points[-1][0]
        self.ys = sorted(point[1] for point in points)
        self.left = self.right = None
        if len(points) > 1:
            middle = len(points) // 2
            self.left = RangeNode(points[:middle])
            self.right = RangeNode(points[middle:])


class DepotRangeTree:
    def __init__(self, points):
        ordered = sorted(points)
        if len({point[2] for point in ordered}) != len(ordered):
            raise ValueError("duplicate depot ID")
        self.root = RangeNode(ordered) if ordered else None

    def count(self, x_low, x_high, y_low, y_high):
        if x_low > x_high or y_low > y_high:
            raise ValueError("inverted half-open window")

        def visit(node):
            if node is None or node.high_x < x_low or node.low_x >= x_high:
                return 0
            if x_low <= node.low_x and node.high_x < x_high:
                return bisect_left(node.ys, y_high) - bisect_left(node.ys, y_low)
            return visit(node.left) + visit(node.right)

        return visit(self.root)


depots = DepotRangeTree([(47, 52, "pump-47"), (19, 61, "valve-19"),
                         (52, 58, "sensor-61"), (180, 70, "grid-83"),
                         (47, 64, "bay-29")])
print(depots.count(15, 60, 45, 65), depots.count(47, 48, 60, 65))

Output

Output
4 1

Time, space, and tradeoff

Sorting the points costs O(N log N). This direct implementation sorts each node's y list again, giving O(N log-squared N) build time and O(N log N) stored y entries. A query visits O(log N) fully covered canonical subtrees, each with two O(log N) y searches, so O(log-squared N) query time and O(log N) recursion space in a balanced tree. The extra per-level y storage is the price of fast orthogonal counting. A simple static two-dimensional prefix grid may be cheaper for a small dense integer domain; a moving-point hash grid suits frequent updates better. No nearest-neighbor or arbitrary polygon claim follows from this rectangle counter.

Common Mistakes

  • Do not count a parent and its children in the same query.
  • Do not use inclusive upper bounds when the API specifies half-open windows.
  • Do not update only a leaf after a point moves.
  • Do not describe this counting API as nearest-neighbor search.

Connected lessons

Compare its update and query contract with Van Emde Boas trees: successor in a bounded integer universe, Scapegoat trees: rebuild a deep insertion subtree, Static XOR filters: peel a fingerprint membership index, then complete the structure audit and decision quiz.

Compressed 2D Fenwick trees: toggle known points and count rectangles adds a distinct structure contract to compare.

Priority search trees: report events in a three-sided region adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details