Advanced Trees

"Fenwick tree, segment tree, sqrt decomposition, Mo's algorithm, treap."

Deep Dive Tutorial

When a problem needs repeated range queries (sum, min, max) with point updates, a flat array is O(n) per query and a prefix sum is O(n) per update. Both Fenwick tree and Segment tree give O(log n) for both operations — the choice is between simplicity (Fenwick, only works for invertible operations) and generality (Segment, works for anything).

Structure	Build	Query	Update	Supports
Prefix Sum	O(n)	O(1)	O(n)	Sum only, no updates
Fenwick (BIT)	O(n log n)	O(log n)	O(log n)	Prefix sum, invertible ops
Segment Tree	O(n)	O(log n)	O(log n)	Sum, min, max, GCD, any associative op
Seg Tree + Lazy	O(n)	O(log n)	O(log n)	Range updates (add, set)

Fenwick Tree (Binary Indexed Tree)

lightbulb

The key trick: i & (-i) isolates the lowest set bit of i. In Fenwick tree:
- Update: travel up by adding i & (-i) — propagates change to all ancestors
- Query: travel down by subtracting i & (-i) — sums up all relevant ranges

Fenwick Tree — point update, prefix sum query

class FenwickTree {
    constructor(n) {
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
    }
    update(i, delta) {    // 1-indexed
        for (; i <= this.n; i += i & (-i))
            this.tree[i] += delta;
    }
    query(i) {             // prefix sum [1..i]
        let sum = 0;
        for (; i > 0; i -= i & (-i))
            sum += this.tree[i];
        return sum;
    }
    rangeQuery(l, r) {     // sum [l..r]
        return this.query(r) - this.query(l - 1);
    }
}

Segment Tree

Segment Tree — range sum, point update

class SegmentTree {
    constructor(arr) {
        this.n = arr.length;
        this.tree = new Array(4 * this.n).fill(0);
        this.build(arr, 0, 0, this.n - 1);
    }
    build(arr, node, start, end) {
        if (start === end) { this.tree[node] = arr[start]; return; }
        const mid = (start + end) >> 1;
        this.build(arr, 2*node+1, start, mid);
        this.build(arr, 2*node+2, mid+1, end);
        this.tree[node] = this.tree[2*node+1] + this.tree[2*node+2];
    }
    update(node, start, end, idx, val) {
        if (start === end) { this.tree[node] = val; return; }
        const mid = (start + end) >> 1;
        if (idx <= mid) this.update(2*node+1, start, mid, idx, val);
        else this.update(2*node+2, mid+1, end, idx, val);
        this.tree[node] = this.tree[2*node+1] + this.tree[2*node+2];
    }
    query(node, start, end, l, r) {
        if (r < start || end < l) return 0;      // out of range
        if (l <= start && end <= r) return this.tree[node]; // full overlap
        const mid = (start + end) >> 1;
        return this.query(2*node+1, start, mid, l, r)
             + this.query(2*node+2, mid+1, end, l, r);
    }
    // Public API
    set(idx, val) { this.update(0, 0, this.n-1, idx, val); }
    sum(l, r) { return this.query(0, 0, this.n-1, l, r); }
}

Worked Problems

Range Sum Query — Mutable

Medium

Solve ↗

Count of Smaller Numbers After Self

Hard