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

Compressed 2D Fenwick trees: toggle known points and count rectangles

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

A compressed two-dimensional Fenwick tree fixes all possible point coordinates before updates begin. Each x Fenwick node catalogs the y coordinates that could contribute to it and owns a local y Fenwick array. Toggling a known point visits its O(log M) x ancestors and updates one y index within each. A two-dimensional prefix query visits x predecessors and asks each local y array for the count below a y boundary. Four prefix results give a half-open rectangle count. This model stores presence as zero or one; repeated activation or removal returns false rather than changing multiplicity. New coordinates need a full catalog rebuild, even if the outer x value already exists.

Operational case

A catalog lists five possible depot points, including two with x equal to 47. Four are active. Rectangle [15,60) by [45,65) contains three active points. Removing (47,61) lowers the answer to two without rebuilding the y catalogs. A point at x equal to 60 or y equal to 65 would be excluded. If an update tried an unlisted coordinate, it would fail explicitly instead of silently losing its value in a missing inner Fenwick array. The index counts active points, not weights or nearest-neighbor distances.

Working Python program

python
from bisect import bisect_left


class DepotPresenceGrid:
    def __init__(self, possible_points):
        self.points = set(possible_points)
        self.x_values = sorted({x for x, _ in self.points})
        self.y_values = [[] for _ in range(len(self.x_values) + 1)]
        for x, y in self.points:
            slot = bisect_left(self.x_values, x) + 1
            while slot < len(self.y_values):
                self.y_values[slot].append(y)
                slot += slot & -slot
        self.y_values = [sorted(set(values)) for values in self.y_values]
        self.bits = [[0] * (len(values) + 1) for values in self.y_values]
        self.present = set()

    def set_present(self, x, y, enabled):
        point = (x, y)
        if point not in self.points:
            raise KeyError("coordinate absent from frozen catalog")
        if (point in self.present) == enabled:
            return False
        if enabled:
            self.present.add(point)
        else:
            self.present.remove(point)
        delta = 1 if enabled else -1
        slot = bisect_left(self.x_values, x) + 1
        while slot < len(self.y_values):
            position = bisect_left(self.y_values[slot], y) + 1
            while position < len(self.bits[slot]):
                self.bits[slot][position] += delta
                position += position & -position
            slot += slot & -slot
        return True

    def _prefix(self, x_limit, y_limit):
        result = 0
        slot = bisect_left(self.x_values, x_limit)
        while slot:
            position = bisect_left(self.y_values[slot], y_limit)
            while position:
                result += self.bits[slot][position]
                position -= position & -position
            slot -= slot & -slot
        return result

    def rectangle_count(self, x_low, x_high, y_low, y_high):
        if x_low > x_high or y_low > y_high:
            raise ValueError("reversed rectangle")
        return (self._prefix(x_high, y_high) - self._prefix(x_low, y_high)
                - self._prefix(x_high, y_low) + self._prefix(x_low, y_low))


if __name__ == "__main__":
    grid = DepotPresenceGrid([(19, 47), (29, 61), (47, 19), (47, 61), (83, 29)])
    for point in [(19, 47), (29, 61), (47, 19), (47, 61)]:
        grid.set_present(*point, True)
    print("active in [15,60) x [45,65):", grid.rectangle_count(15, 60, 45, 65))
    grid.set_present(47, 61, False)
    print("after removal:", grid.rectangle_count(15, 60, 45, 65))

Output

Output
active in [15,60) x [45,65): 3
after removal: 2

Time, space, and tradeoff

Let M be the number of possible points. Every point is copied into O(log M) y catalogs, using O(M log M) stored coordinate entries and Fenwick cells. The direct construction sorts and deduplicates each catalog, with O(M log-squared M) upper-bound time. Toggling and rectangle counting take O(log-squared M) time and O(1) extra query memory beyond those catalogs. Python lists and tuples carry overhead. A dense fixed-grid Fenwick array may be simpler for a small domain; a static range tree can answer counts without supporting live toggles.

Common Mistakes

  • Do not update a coordinate omitted from the frozen catalog.
  • Do not count upper rectangle boundaries in half-open queries.
  • Do not toggle an already active point as though duplicates were supported.
  • Do not confuse sparse coordinate storage with a fully open coordinate universe.

Connected lessons

Compare its update and query contract with Linear hashing: split one bucket at a time as a table grows, Persistent two-list queues: fork FIFO dispatch history, Balanced-parentheses trees: encode an ordered hierarchy, then complete the structure audit and decision quiz.

data structures
range-query-structures
Storage details