Fenwick Tree (Binary Indexed Tree)

Also Known As

TL;DR

Explanation

A Fenwick Tree, also called a Binary Indexed Tree (BIT), is a 1-indexed array where each cell stores the sum of a power-of-two-sized range of original values. The size of that range is determined by the lowest set bit of the index, so traversal up or down the implicit tree is done with simple bit tricks: `i += i & -i` to move to the next responsible parent during updates, and `i -= i & -i` to walk prefix segments during queries. Both operations are O(log n), and the structure uses exactly n+1 array slots with no node objects or pointers. Fenwick Trees solve the classic running-totals problem: given an array that mutates over time, answer 'what is the sum of elements 1..k?' or 'what is the sum of elements l..r?' (via two prefix queries) without rescanning. Compared to a Segment Tree, Fenwick is roughly half the code, half the memory, and slightly faster in practice for pure prefix-sum workloads, at the cost of being harder to extend to arbitrary range queries like min/max. Common applications include real-time leaderboard scoring, inversion counting in merge-sort-style algorithms, cumulative frequency tables for statistics, and order-book or analytics rollups where individual cells change frequently and dashboards need fast aggregates. The structure can be generalised: 2D Fenwick Trees support O(log n * log m) updates on a grid, and range-update/range-query variants exist using two parallel BITs. For databases, you would typically use MySQL window functions for one-off rollups, but a Fenwick Tree wins when updates and queries are interleaved at high frequency in application memory.

Common Misconception

Why It Matters

Common Mistakes

• Using 0-based indexing internally — the `i & -i` trick requires 1-based indices, and a zero index loops forever.
• Trying to support non-invertible operations like min or max — Fenwick relies on subtraction to derive range queries, so use a segment tree for those.
• Forgetting to size the array as n+1, causing off-by-one overflows at the last index.
• Rebuilding the tree on every update instead of using the O(log n) update path.
• Computing range sums as a single walk instead of `prefix(r) - prefix(l-1)`.

Code Examples

<?php
// Naive: O(n) per range-sum query, O(1) per update.
// Fine for a few hundred rows; collapses on hot leaderboards.
class LeaderboardNaive {
    private array $scores; // 1-indexed
    private int $n;

    public function __construct(int $n) {
        $this->n = $n;
        $this->scores = array_fill(0, $n + 1, 0);
    }

    public function update(int $userId, int $delta): void {
        $this->scores[$userId] += $delta;
    }

    // O(n) — walks the whole prefix every call.
    public function topRankCumulative(int $rank): int {
        $sum = 0;
        for ($i = 1; $i <= $rank; $i++) {
            $sum += $this->scores[$i];
        }
        return $sum;
    }
}

// MySQL equivalent that re-scans on every dashboard refresh:
// SELECT SUM(score) FROM leaderboard WHERE rank <= ?;
// Each call is O(n) in the index range — no incremental structure.

<?php
// Fenwick Tree: O(log n) update, O(log n) prefix query.
final class FenwickTree {
    private array $tree;
    private int $n;

    public function __construct(int $n) {
        $this->n = $n;
        $this->tree = array_fill(0, $n + 1, 0); // 1-indexed
    }

    public function update(int $i, int $delta): void {
        for (; $i <= $this->n; $i += $i & -$i) {
            $this->tree[$i] += $delta;
        }
    }

    public function prefixSum(int $i): int {
        $sum = 0;
        for (; $i > 0; $i -= $i & -$i) {
            $sum += $this->tree[$i];
        }
        return $sum;
    }

    public function rangeSum(int $l, int $r): int {
        return $this->prefixSum($r) - $this->prefixSum($l - 1);
    }
}

// Usage: leaderboard cumulative scores in-memory, mirrored from MySQL.
// CREATE TABLE leaderboard (user_id INT PRIMARY KEY, score INT);
// On score change: $bit->update($userId, $delta) plus single-row UPDATE.
// Dashboard 'sum of top K ranks' is now O(log n) instead of O(n).

References

• https://en.wikipedia.org/wiki/Fenwick_tree
• https://cp-algorithms.com/data_structures/fenwick.html
• https://dl.acm.org/doi/10.1002/spe.4380240306

Tags

🧠 Logic Engine