# Fenwick Tree (BIT) — डेटा स्ट्रक्चर और एल्गोरिदम

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

> Prefix sums और point updates के लिए compact array-based structure, O(log n) में, segment tree से सरल।

## तरकीब

**Binary Indexed Tree (Fenwick tree)** आंशिक sums को उन indices पर रखता है जो `i` के **सबसे कम set bit** से चुने जाते हैं। Index `i`, `i & (-i)` आकार की range के लिए ज़िम्मेदार होता है। इससे update और prefix-sum दोनों केवल एक array से `O(log n)` में चलते हैं।

## Update और prefix sum

`update` `i & -i` जोड़ते हुए ऊपर जाता है; `prefix_sum` इसे घटाते हुए नीचे जाता है। Range sum है `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 बनाम segment tree

Fenwick tree लिखने में छोटा है और आधी memory लेता है, पर स्वाभाविक रूप से केवल **prefix-reducible** operations (जैसे sum/xor) को support करता है। Segment tree min/max/gcd और range updates तक सामान्यीकृत होता है — sum के लिए Fenwick चुनें, बाकी के लिए segment tree।

## त्वरित जांच

सही time complexity चुनें।

**Quiz:** Fenwick tree के update और prefix-sum operations चलते हैं:

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

*Answer:* O(log n). दोनों index को सबसे कम set bit बदलते हुए ऊपर/नीचे जाते हैं, O(log n) चरणों में।