# Fenwick Tree (BIT) — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/fenwick-tree

> A compact array-based structure for prefix sums and point updates in O(log n), simpler than a segment tree.

## The trick

A **Binary Indexed Tree (Fenwick tree)** stores partial sums at indices chosen by the **lowest set bit** of `i`. Index `i` is responsible for a range of size `i & (-i)`. This lets both update and prefix-sum run in `O(log n)` using only a single array.

## Update & prefix sum

`update` walks up adding `i & -i`; `prefix_sum` walks down subtracting it. A range sum is `prefix_sum(r) - prefix_sum(l-1)`.

```python
bit = [0] * (n + 1)

def update(i, delta):
    while i <= n:
        bit[i] += delta
        i += i & (-i)

def prefix_sum(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & (-i)
    return s

def range_sum(l, r):
    return prefix_sum(r) - prefix_sum(l - 1)
```

Output:

```
update(3, 5)
range_sum(1, 3)  # includes the +5 at index 3
```

## Fenwick vs segment tree

Fenwick trees are shorter to code and use half the memory, but only naturally support **prefix-reducible** operations like sum/xor. Segment trees generalize to min/max/gcd and range updates — pick Fenwick for sums, segment tree for everything else.

## Quick check

Pick the correct time complexity.

**Quiz:** A Fenwick tree's update and prefix-sum operations run in:

- [ ] O(1)
- [x] O(log n)
- [ ] O(n)
- [ ] O(n log n)

*Answer:* O(log n). Both walk up/down the index by flipping the lowest set bit, taking O(log n) steps.