Fenwick Tree (BIT)

तरकीब

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)।

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 चुनें।

त्वरित जाँच: Fenwick tree के update और prefix-sum operations चलते हैं:

• O(1)
• O(log n)
• O(n)
• O(n log n)