Advanced Tree Structures

"Segment tree for range queries. Fenwick for prefix sums. O(log n) both."

Segment trees and Fenwick/Binary Indexed Trees solve range queries and point updates in O(log n). Learn when to use each, how to build them, and the lazy propagation pattern for range updates.

20 min readadvanced tree problems →

Problems you can solve with this pattern

4 problems · click any to start solving

All advanced tree →

1Range Sum Query — MutableMediumSolve

2Count of Smaller Numbers After SelfHardSolve

4Range Sum Query — MutableMediumSolve

5Longest Increasing Subsequence (with BIT for O(n log n))MediumSolve

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);
    }
}

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)

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); }
}

Range Sum Query — Mutable

Medium

Solve

Count of Smaller Numbers After Self

Hard

Solve

Range Sum Query — Mutable

Medium

Solve

Longest Increasing Subsequence (with BIT for O(n log n))

Medium

Solve

When to use Fenwick vs Segment Tree:
- Fenwick: simpler code, only works for operations with inverses (sum, xor). Not for min/max.
- Segment Tree: more code, works for ANY associative operation (sum, min, max, GCD, product mod p).

For range UPDATES (add delta to all elements in [l..r]): need lazy propagation on Segment Tree or difference array trick.

← Monotonic Stack & Queue Combinatorics & Counting →