Chapter 100

Home

Fenwick Tree (Binary Indexed Tree)

Fenwick tree (BIT) supports prefix sums and point updates in O(log N). Less flexible than a segment tree (can't do arbitrary range queries easily), but simpler, faster, and uses O(N) memory.

Fenwick Tree for Prefix Sum

C++ — Fenwick tree

struct BIT {
    vector bit;
    int n;

    BIT(int sz) : n(sz), bit(sz + 1, 0) {}

    void add(int idx, long long delta) {
        for (; idx <= n; idx += idx & -idx)
            bit[idx] += delta;
    }

    long long sum(int idx) {  // prefix sum 1..idx
        long long res = 0;
        for (; idx > 0; idx -= idx & -idx)
            res += bit[idx];
        return res;
    }

    long long range_sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
};

// O(log N) per operation. Memory: O(N).
// 1-indexed — simpler with LSB logic.

Rust — BIT

struct BIT {
    bit: Vec,
}
impl BIT {
    fn new(n: usize) -> Self { BIT { bit: vec![0; n + 1] } }
    fn add(&mut self, mut idx: usize, delta: i64) {
        let n = self.bit.len() - 1;
        while idx <= n { self.bit[idx] += delta; idx += idx & idx.wrapping_neg(); }
    }
    fn sum(&self, mut idx: usize) -> i64 {
        let mut res = 0;
        while idx > 0 { res += self.bit[idx]; idx -= idx & idx.wrapping_neg(); }
        res
    }
}

💡 BIT vs Segment Tree

BIT: O(log N), O(N) mem, prefix sums only. SegTree: O(log N), O(4N) mem, arbitrary ranges. Use BIT when you only need prefix queries — it's 3-5× faster in practice.

Key Takeaways