Skip to content

Advanced trees

Tree names matter less than the order they preserve. Start from the operations: ordered keys, shared prefixes, numeric ranges, or geometric regions.

Thinking flow · choose the index

flowchart TD
  accTitle: Choosing an advanced tree structure
  accDescr: Ordered predecessor and successor queries suggest a balanced binary search tree, prefix queries suggest a Trie, point updates with prefix aggregates suggest a Fenwick tree, general associative ranges suggest a segment tree, and low-dimensional nearest or orthogonal spatial queries suggest a KD tree.
  A{"What is the query domain?"}
  A -->|"ordered comparable keys"| B["Balanced BST<br/>red-black / AVL"]
  A -->|"string or token prefixes"| C["Trie"]
  A -->|"numeric index ranges"| D{"Which operations?"}
  D -->|"point add + prefix/group range"| E["Fenwick tree"]
  D -->|"general associative range + updates"| F["Segment tree"]
  A -->|"low-dimensional points"| G["KD tree"]

Smallest range template

A Fenwick tree is the compact first choice for point additions and prefix sums.

class FenwickTree:
    """Support point additions and prefix/range sums in logarithmic time."""

    def __init__(self, size: int) -> None:
        if size < 0:
            raise ValueError("size must be nonnegative")
        self.size = size
        self.tree = [0] * (size + 1)

    def add(self, index: int, delta: int) -> None:
        if not 0 <= index < self.size:
            raise IndexError("index outside Fenwick tree")
        cursor = index + 1
        while cursor <= self.size:
            self.tree[cursor] += delta
            # Add the lowest set bit to reach the next owning range.
            cursor += cursor & -cursor

    def prefix_sum(self, end: int) -> int:
        """Return the sum of the half-open prefix ``[0, end)``."""
        if not 0 <= end <= self.size:
            raise IndexError("prefix end outside Fenwick tree")
        total = 0
        cursor = end
        while cursor:
            total += self.tree[cursor]
            # Remove the lowest set bit to visit the parent prefix.
            cursor -= cursor & -cursor
        return total

    def range_sum(self, left: int, right: int) -> int:
        if not 0 <= left <= right <= self.size:
            raise IndexError("range outside Fenwick tree")
        return self.prefix_sum(right) - self.prefix_sum(left)

class FenwickTree {
 public:
  explicit FenwickTree(int size) : size_(size) {
    if (size < 0) {
      throw std::invalid_argument("size must be nonnegative");
    }
    tree_.assign(static_cast<std::size_t>(size) + 1, 0);
  }

  void add(int index, long long delta) {
    require_index(index);
    for (int cursor = index + 1; cursor <= size_;
         cursor += cursor & -cursor) {
      // Each visited node owns a larger range containing index.
      tree_[cursor] += delta;
    }
  }

  long long prefix_sum(int end) const {
    if (end < 0 || end > size_) {
      throw std::out_of_range("prefix end outside Fenwick tree");
    }
    long long total = 0;
    for (int cursor = end; cursor > 0; cursor -= cursor & -cursor) {
      // Removing the lowest set bit visits the parent prefix.
      total += tree_[cursor];
    }
    return total;
  }

  long long range_sum(int left, int right) const {
    if (left < 0 || left > right || right > size_) {
      throw std::out_of_range("range outside Fenwick tree");
    }
    return prefix_sum(right) - prefix_sum(left);
  }

 private:
  void require_index(int index) const {
    if (index < 0 || index >= size_) {
      throw std::out_of_range("index outside Fenwick tree");
    }
  }

  int size_;
  std::vector<long long> tree_;
};

class FenwickTree {
 public:
  explicit FenwickTree(int size) : size_(size) {
    if (size < 0) {
      throw std::invalid_argument("size must be nonnegative");
    }
    tree_.assign(static_cast<std::size_t>(size) + 1, 0);
  }

  void add(int index, long long delta) {
    require_index(index);
    for (int cursor = index + 1; cursor <= size_;
         cursor += cursor & -cursor) {
      // Each visited node owns a larger range containing index.
      tree_[cursor] += delta;
    }
  }

  long long prefix_sum(int end) const {
    if (end < 0 || end > size_) {
      throw std::out_of_range("prefix end outside Fenwick tree");
    }
    long long total = 0;
    for (int cursor = end; cursor > 0; cursor -= cursor & -cursor) {
      // Removing the lowest set bit visits the parent prefix.
      total += tree_[cursor];
    }
    return total;
  }

  long long range_sum(int left, int right) const {
    if (left < 0 || left > right || right > size_) {
      throw std::out_of_range("range outside Fenwick tree");
    }
    return prefix_sum(right) - prefix_sum(left);
  }

 private:
  void require_index(int index) const {
    if (index < 0 || index >= size_) {
      throw std::out_of_range("index outside Fenwick tree");
    }
  }

  int size_;
  std::vector<long long> tree_;
};

Reading path