Basic Segment Tree & BIT Questions

1. Range sum with point updates

The canonical use. Build a sum segment tree (or a BIT); query(i, j) returns the subrange sum, update(i, v) changes a value — both O(log n). This is exactly Range Sum Query — Mutable. If you only need sums, prefer the BIT for its brevity.

2. Range minimum query (RMQ)

Same segment tree, different aggregate: combine = min, identity = +∞. Now query(i, j) is the smallest element in the subrange.

# only the combine + identity change vs the sum tree
NEG = float('inf')
def _build(self, node, lo, hi):
    if lo == hi: self.tree[node] = self.a[lo]; return
    mid = (lo + hi) // 2
    self._build(2*node, lo, mid); self._build(2*node+1, mid+1, hi)
    self.tree[node] = min(self.tree[2*node], self.tree[2*node+1])   # <- min, not +
# query returns NEG (=+inf) for the disjoint case, else min of the parts

A BIT can’t do general RMQ (min isn’t invertible) — this is the textbook reason to choose a segment tree.

3. The BIT update/query loop by hand

Trace update(i, +1) walking up via i += i & -i and prefixSum(i) walking down via i -= i & -i. For n = 8, update(5, +1) touches indices 5 → 6 → 8; prefixSum(7) sums bit[7] + bit[6] + bit[4]. Doing one trace by hand makes the i & -i jumps click.

4. Count elements ≤ x seen so far (a frequency BIT)

A huge pattern: index the BIT by value instead of position. update(value, +1) records “I’ve seen this value”; prefixSum(x) counts how many seen values are ≤ x. This turns “how many earlier elements are smaller?” into a BIT query — the engine behind Count of Smaller Numbers After Self.

5. Coordinate compression

When values are huge or sparse (up to 10^9) but there are only n ≤ 10^5 of them, you can’t index a BIT by raw value. Compress: collect all values, sort + dedupe, and map each to its rank (0, 1, 2, …). Now index by rank — the BIT only needs size n.

def compress(values):
    order = sorted(set(values))
    rank = {v: i + 1 for i, v in enumerate(order)}   # 1-indexed for the BIT
    return rank                                       # use rank[v] as the BIT index

This preprocessing is mandatory for value-indexed BIT/segment-tree problems with large ranges.

6. Range update via difference array

To “add v to all of [i, j]” with only point-update tooling, store deltas: update(i, +v), update(j+1, −v). A prefix sum then reconstructs the value at any index. The lightweight version of lazy propagation when you only need point reads after range updates.