DSA — Fenwick Tree

What is a Fenwick Tree?

A data structure for efficiently computing prefix sums and updating values.

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)
    
    def query(self, i):
        sum = 0
        while i > 0:
            sum += self.tree[i]
            i -= i & (-i)
        return sum

Range Sum Query

def range_query(self, l, r):
    return self.query(r) - self.query(l - 1)

Build from Array

def build(self, arr):
    for i in range(1, len(arr) + 1):
        self.update(i, arr[i - 1])

Time Complexity

Operation	Complexity
Update	O(log n)
Query	O(log n)
Build	O(n log n)

Applications

• Prefix sum queries
• Range sum queries
• Inversion counting
• Binary indexed operations

Comparison with Segment Tree

Feature	Fenwick Tree	Segment Tree
Implementation	Simpler	More complex
Space	O(n)	O(n)
Constant factor	Smaller	Larger
Range updates	Harder	Easier

Mini Practice

1. Implement Fenwick Tree
2. Compute prefix sums
3. Update and query
4. Count inversions

Up Next

Congratulations! You've completed the DSA course. Continue practicing problems on LeetCode and HackerRank.