Fenwick tree / segment tree

How does Fenwick tree / segment tree work?

Each node of the tree owns a range and stores its answer. The root owns the whole array.

A node's answer is built from its two children. The combining rule is sum, min, max or something similar.

A query splits the wanted range against the tree. It stops at any node that lies fully inside.

At most two nodes per level are ever needed. That gives log n work per query.

An update changes one leaf and walks back to the root. Only the nodes above that leaf change.

A Fenwick tree does the same for prefix sums with far less code. A segment tree also handles min, max and lazy updates.

1. leaves: 3, 1, 4, 1The array is [3, 1, 4, 1]. Each leaf owns one position.
2. level above: 4 and 5Each node sums its own two children.
3. root = 9The root holds the total of the whole array.
4. query 1 to 2The wanted range is 1 plus 4. Two nodes cover it exactly.
5. set index 1 to 6One leaf and two nodes above it change. The root becomes 14.

class Fenwick {
    constructor(n) { this.tree = new Array(n + 1).fill(0); }
    update(i, delta) {
        for (; i < this.tree.length; i += i & -i) this.tree[i] += delta;
    }
    query(i) {
        let sum = 0;
        for (; i > 0; i -= i & -i) sum += this.tree[i];
        return sum;
    }
}

A worked example of Fenwick tree / segment tree

Count the smaller values to the right

For every element, count how many later elements are smaller than it.

A nested loop is O(n squared) and dies at 1e5 elements.

Walk the array from the right, keeping a Fenwick tree over the values.

For each element, ask how many smaller values are recorded already. Then record this one.

function countSmaller(nums) {
    const sorted = [...new Set(nums)].sort((a, b) => a - b);
    const rank = new Map(sorted.map((v, i) => [v, i + 1])); // ranks start at 1

    const tree = new Array(sorted.length + 1).fill(0);

    const add = (i) => {
        for (; i < tree.length; i += i & -i) tree[i]++;
    };

    const countBelow = (i) => {
        let total = 0;
        for (; i > 0; i -= i & -i) total += tree[i];
        return total;
    };

    const answer = new Array(nums.length);
    for (let i = nums.length - 1; i >= 0; i--) {
        const r = rank.get(nums[i]);
        answer[i] = countBelow(r - 1); // strictly smaller values already seen
        add(r);
    }

    return answer;
}

When should you use Fenwick tree / segment tree?

These phrases in a problem statement point here:

• •range sum or query with point updates interleaved
• •live leaderboard or running rank while scores change
• •count inversions or how many earlier values are larger
• •range queries while the data keeps changing

What is Fenwick tree / segment tree confused with?

• Prefix sums: Prefix sums read faster but break on any change. This pays log n to allow updates.
• Difference array: That takes many range updates and one read at the end. Here reads and writes are mixed.
• Sweep line (event counting): A sweep processes events in sorted order and never looks back. Here queries arrive in any order.
• Binary search (array): Both halve a range each step. One hunts a value, this one aggregates over a range.

Common mistakes with Fenwick tree / segment tree

• Indexing a Fenwick tree from zero

  The low-bit step needs indices to start at one. A zero index loops forever.

• Using it where nothing ever changes

  A prefix array answers in O(1) and costs nothing to read. Pay for a tree only when updates arrive.

• Forgetting to compress the values

  A tree sized by the value range dies on values up to 1e9. Map them to ranks first.

• Combining ranges with a rule that does not fit

  Sum and min work because order does not matter to them. An order-dependent rule needs more per node.

Which interview problems use Fenwick tree / segment tree?

• Range sum query mutable: Reads and writes mixed together in any order.
• Count of smaller numbers after self: A Fenwick tree over compressed ranks.
• Count of range sum: Prefix sums fed into the tree.
• Reverse pairs: Merge sort or a Fenwick tree, either works.
• Range minimum query: A segment tree, since min has no inverse.
• Range sum query 2D mutable: A tree whose nodes are themselves trees.
• My calendar II: A segment tree with lazy range updates.

What is the time and space complexity of Fenwick tree / segment tree?

O(log n) per op

n up to 1e6 with q mixed operations gives O((n + q) log n). Memory is O(n) for a Fenwick tree.