14. Advanced Structures

Key Insight

These structures solve problems that heaps and sorted arrays cannot: range updates + queries in $O(\log n)$ and weighted union-find with rollback. In CP, segment trees and BITs appear in roughly 20–30% of medium-hard problems.

---

14.1 Fenwick Tree (Binary Indexed Tree / BIT)

Supports: prefix sum query and point update in $O(\log n)$.
Best for: frequency tables, inversion count, order statistics.

class BIT:
    """1-indexed Fenwick tree for prefix sums."""
    def __init__(self, n: int):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i: int, delta: int) -> None:
        """Add delta to position i (1-indexed)."""
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)   # move to parent

    def query(self, i: int) -> int:
        """Prefix sum [1..i]."""
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)   # move to predecessor
        return s

    def range_query(self, l: int, r: int) -> int:
        """Sum of [l..r] (1-indexed)."""
        return self.query(r) - self.query(l - 1)

    def build(self, arr: list[int]) -> None:
        """Build from array in O(n)."""
        for i, v in enumerate(arr, 1):
            self.update(i, v)

# --- Count inversions using BIT --- O(n log n)
def count_inversions_bit(arr: list[int]) -> int:
    # Coordinate compress
    sorted_unique = sorted(set(arr))
    rank = {v: i+1 for i, v in enumerate(sorted_unique)}
    bit = BIT(len(sorted_unique))
    inversions = 0
    for x in reversed(arr):
        r = rank[x]
        inversions += bit.query(r - 1)   # elements smaller than x seen so far (to the right)
        bit.update(r, 1)
    return inversions

# --- 2D BIT (for 2D range sum updates/queries) ---
class BIT2D:
    def __init__(self, m: int, n: int):
        self.m, self.n = m, n
        self.tree = [[0] * (n + 1) for _ in range(m + 1)]

    def update(self, r: int, c: int, delta: int) -> None:
        i = r
        while i <= self.m:
            j = c
            while j <= self.n:
                self.tree[i][j] += delta
                j += j & (-j)
            i += i & (-i)

    def query(self, r: int, c: int) -> int:
        s = 0; i = r
        while i > 0:
            j = c
            while j > 0:
                s += self.tree[i][j]
                j -= j & (-j)
            i -= i & (-i)
        return s

---

14.2 Segment Tree

Supports: range queries (sum, min, max) and point/range updates in $O(\log n)$.

class SegTree:
    """
    1-indexed segment tree for range sum + point update.
    To adapt: change merge() and identity value.
    """
    def __init__(self, n: int):
        self.n = n
        self.tree = [0] * (4 * n)

    def build(self, arr: list[int], node: int = 1, lo: int = 1, hi: int = -1) -> None:
        if hi == -1: hi = self.n
        if lo == hi:
            self.tree[node] = arr[lo - 1]; return
        mid = (lo + hi) // 2
        self.build(arr, 2*node,   lo,    mid)
        self.build(arr, 2*node+1, mid+1, hi)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]  # merge

    def update(self, idx: int, val: int, node: int = 1, lo: int = 1, hi: int = -1) -> None:
        if hi == -1: hi = self.n
        if lo == hi:
            self.tree[node] = val; return
        mid = (lo + hi) // 2
        if idx <= mid:
            self.update(idx, val, 2*node,   lo,    mid)
        else:
            self.update(idx, val, 2*node+1, mid+1, hi)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]

    def query(self, l: int, r: int, node: int = 1, lo: int = 1, hi: int = -1) -> int:
        if hi == -1: hi = self.n
        if l > hi or r < lo: return 0   # identity for sum
        if l <= lo and hi <= r: return self.tree[node]
        mid = (lo + hi) // 2
        return (self.query(l, r, 2*node,   lo,    mid) +
                self.query(l, r, 2*node+1, mid+1, hi))

---

14.3 Segment Tree with Lazy Propagation

Use when: range update + range query (e.g., add $v$ to all elements in [l,r], then query sum of [l,r]).

class LazySegTree:
    """Range add + range sum query."""
    def __init__(self, n: int):
        self.n = n
        self.tree  = [0] * (4 * n)
        self.lazy  = [0] * (4 * n)

    def _push_down(self, node: int, lo: int, hi: int) -> None:
        if self.lazy[node]:
            mid = (lo + hi) // 2
            self._apply(2*node,   lo,    mid, self.lazy[node])
            self._apply(2*node+1, mid+1, hi,  self.lazy[node])
            self.lazy[node] = 0

    def _apply(self, node: int, lo: int, hi: int, val: int) -> None:
        self.tree[node] += val * (hi - lo + 1)
        self.lazy[node] += val

    def build(self, arr: list[int], node: int = 1, lo: int = 1, hi: int = -1) -> None:
        if hi == -1: hi = self.n
        if lo == hi:
            self.tree[node] = arr[lo-1]; return
        mid = (lo + hi) // 2
        self.build(arr, 2*node,   lo,    mid)
        self.build(arr, 2*node+1, mid+1, hi)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]

    def update(self, l: int, r: int, val: int, node: int = 1, lo: int = 1, hi: int = -1) -> None:
        if hi == -1: hi = self.n
        if l > hi or r < lo: return
        if l <= lo and hi <= r:
            self._apply(node, lo, hi, val); return
        self._push_down(node, lo, hi)
        mid = (lo + hi) // 2
        self.update(l, r, val, 2*node,   lo,    mid)
        self.update(l, r, val, 2*node+1, mid+1, hi)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]

    def query(self, l: int, r: int, node: int = 1, lo: int = 1, hi: int = -1) -> int:
        if hi == -1: hi = self.n
        if l > hi or r < lo: return 0
        if l <= lo and hi <= r: return self.tree[node]
        self._push_down(node, lo, hi)
        mid = (lo + hi) // 2
        return (self.query(l, r, 2*node,   lo,    mid) +
                self.query(l, r, 2*node+1, mid+1, hi))

---

14.4 DSU with Rollback (for offline queries)

Use when: need to undo union operations (e.g., divide-and-conquer on timeline).

class DSU_Rollback:
    """Union by rank, NO path compression (needed for rollback)."""
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank   = [0] * n
        self.history: list[tuple] = []   # (node, old_parent, node, old_rank)

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x: int, y: int) -> bool:
        px, py = self.find(x), self.find(y)
        if px == py:
            self.history.append(None)   # no-op marker
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.history.append((py, self.parent[py], px, self.rank[px]))
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

    def rollback(self) -> None:
        entry = self.history.pop()
        if entry is None: return
        py, old_parent_py, px, old_rank_px = entry
        self.parent[py] = old_parent_py
        self.rank[px]   = old_rank_px

---

14.5 Sparse Table (Static Range Minimum Query)

$O(n \log n)$ build, $O(1)$ query. Read-only (no updates).

import math

class SparseTable:
    def __init__(self, arr: list[int]):
        n = len(arr)
        LOG = max(1, math.floor(math.log2(n)) + 1) if n > 0 else 1
        self.log2 = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log2[i] = self.log2[i // 2] + 1
        self.table = [[float("inf")] * n for _ in range(LOG)]
        self.table[0] = arr[:]
        for j in range(1, LOG):
            for i in range(n - (1 << j) + 1):
                self.table[j][i] = min(self.table[j-1][i],
                                        self.table[j-1][i + (1 << (j-1))])

    def query(self, l: int, r: int) -> int:
        """Minimum of arr[l..r] inclusive, O(1)."""
        k = self.log2[r - l + 1]
        return min(self.table[k][l], self.table[k][r - (1 << k) + 1])

---

14.6 Key CP Patterns

Structure	Query	Update	Best for
BIT	Prefix sum $O(\log n)$	Point $O(\log n)$	Inversions, order stats
Segment tree	Range $O(\log n)$	Point $O(\log n)$	Range min/max/sum
Lazy seg tree	Range $O(\log n)$	Range $O(\log n)$	Range assign/add
Sparse table	Range min/max $O(1)$	None	Static RMQ, LCA
DSU rollback	—	—	Offline connectivity undo

---