Fenwick Tree (Binary Indexed Tree)

1. One-Liner

A Fenwick tree maintains prefix sums with point updates in O(log n) using a clever indexing pattern (i ± (i & -i)).

2. The Problem It Solves

You need dynamic prefix sums or inversion counts without coding a full segment tree. BIT gives shorter code and better constants for additive aggregates on a 1-based index array.

3. The Core Idea

Each index i stores sum of a range of length lowbit(i) ending at i. Update walks upward adding lowbit; prefix query walks upward subtracting lowbit. Range [l,r] = prefix(r) − prefix(l−1).

4. How It Works (Step-by-Step)

Step	Action
1	Use 1-based `bit[1…n]`.
2	`add(i, d)`: for (`j=i; j≤n; j+=j&-j`) `bit[j]+=d`.
3	`sum(i)`: accumulate `bit[j]` for (`j=i; j>0; j-=j&-j`).
4	Range sum = `sum(r) - sum(l-1)`.

5. Dry Run Example

Start zeros; add(3,5) touches indices 3,4,8…; sum(4) aggregates 4+3 contributions—matches array prefix.

6. Key Properties

Fact	Detail
lowbit	`i & -i` (LSB)
2D BIT	Nested loops extension
Not	General min without tricks

7. Where It Is Used

Use	Why
Inversion count	Pair frequencies
CF problems	Fast cumulative freq
Online contests	Tiny code

8. Interview Tips

Prove why ranges partition uniquely. Show mapping from array index to tree. Mention coordinate compression when values huge.

9. Comparison with Other Algorithms

DS	Flexibility	Code length
Fenwick	Sums (multiplicative with log)	Short
Segment tree	General monoid + lazy	Longer
Prefix array	Static only	Shortest

10. Complexity


--	--
Update / Query	O(log n)
Space	O(n)

Implementation Example (PYTHON)

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)
    def _i(self, i): return i & -i
    def add(self, i, d):
        while i <= self.n:
            self.bit[i] += d
            i += self._i(i)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= self._i(i)
        return s