Fenwick tree / segment tree

How does Fenwick tree / segment tree work?

A Fenwick tree stores partial sums in an array indexed from 1. tree[i] covers a block that ends at i.

The block length is the lowest set bit of i, written i & -i. So tree[4] covers 1 to 4, and tree[6] covers 5 and 6.

query(i) adds tree[i], then removes the lowest bit from i. It repeats until i reaches zero and returns the prefix sum.

update(i) adds the change to tree[i], then adds the lowest bit to i. Every block that contains position i gets the change.

Both loops touch about log n cells. A range sum is query(r) minus query(l - 1).

A segment tree keeps one node per range, and its sum comes from two children. A query stops at every node that lies fully inside the range.

A segment tree takes more code than a Fenwick tree. In return it also handles min, max and lazy range updates.

Sources: Wikipedia: Fenwick tree, Wikipedia: Segment tree, Fenwick (1994), A new data structure for cumulative frequency tables

1. tree = [3, 4, 4, 9]The array is [3, 1, 4, 1], indexed from 1. tree[4] covers all four.
2. query(3): tree[3] + tree[2]3 loses its lowest bit and becomes 2. So far 4 plus 4.
3. query(3) = 82 loses its lowest bit and becomes 0. The sum 8 is 3 + 1 + 4.
4. update(2, +5): tree[2] and tree[4]2 plus its lowest bit is 4, and 8 is past the end. Two cells change.
5. sum of 2 to 3 = 13 - 3 = 10query(3) is now 13 and query(1) is 3. Subtracting gives the range.

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

class Fenwick {
    private tree: number[];

    constructor(n: number) {
        this.tree = new Array<number>(n + 1).fill(0);
    }

    update(i: number, delta: number): void {
        for (; i < this.tree.length; i += i & -i) this.tree[i] += delta;
    }

    query(i: number): number {
        let sum = 0;
        for (; i > 0; i -= i & -i) sum += this.tree[i];
        return sum;
    }
}

class Fenwick:
    def __init__(self, n):
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & -i

    def query(self, i):
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i
        return total

class Fenwick {
    private array $tree;
    public function __construct(int $n) { $this->tree = array_fill(0, $n + 1, 0); }
    public function update(int $i, int $delta): void {
        for (; $i < count($this->tree); $i += $i & -$i) $this->tree[$i] += $delta;
    }
    public function query(int $i): int {
        $sum = 0;
        for (; $i > 0; $i -= $i & -$i) $sum += $this->tree[$i];
        return $sum;
    }
}

    public static class Fenwick {
        private final int[] tree;

        public Fenwick(int n) {
            tree = new int[n + 1];
        }

        public void update(int i, int delta) {
            for (; i < tree.length; i += i & -i) tree[i] += delta;
        }

        public int query(int i) {
            int sum = 0;
            for (; i > 0; i -= i & -i) sum += tree[i];
            return sum;
        }
    }

    public class Fenwick {
        private readonly int[] tree;

        public Fenwick(int n) {
            tree = new int[n + 1];
        }

        public void Update(int i, int delta) {
            for (; i < tree.Length; i += i & -i) tree[i] += delta;
        }

        public int Query(int i) {
            int sum = 0;
            for (; i > 0; i -= i & -i) sum += 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?

Use Fenwick tree / segment tree when the problem statement says “range sum or query with point updates interleaved”, “live leaderboard or running rank while scores change” or “count inversions or how many earlier values are larger”. A solution built on it usually runs in O(log n) per op.

• •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

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Fenwick tree / segment tree confused with?

Fenwick tree / segment tree is most often confused with Prefix sums, Difference array, Sweep line (event counting) and Binary search (array).

• 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?

Interview problems solved with Fenwick tree / segment tree include Range sum query mutable, Count of smaller numbers after self, Count of range sum, Reverse pairs, Range minimum query, Range sum query 2D mutable and My calendar II.

• 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?

The target complexity of Fenwick tree / segment tree is 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.