What is a Fenwick Tree?

A Fenwick Tree, also known as a Binary Indexed Tree (BIT), is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. It allows both operations to be performed in O(log n) time.

When should I use a Fenwick Tree over a Segment Tree?

A Fenwick Tree is a good choice when you need to perform point updates and range sum queries (or any other operation that is invertible). It is simpler to implement and has a smaller constant factor than a Segment Tree. However, a Segment Tree is more versatile and can handle a wider range of queries, such as range minimum/maximum queries.

Data Structures

Fenwick Tree (Binary Indexed Tree)

An efficient data structure for calculating prefix sums and performing point updates, offering logarithmic time complexity for both operations.

Fenwick Tree in Python

Here is a Python implementation of a Fenwick Tree (BIT) that supports point updates and prefix sum queries.

class FenwickTree:
    def __init__(self, size):
        self.tree = [0] * (size + 1)

    def update(self, index, delta):
        index += 1
        while index < len(self.tree):
            self.tree[index] += delta
            index += index & -index

    def query(self, index):
        index += 1
        s = 0
        while index > 0:
            s += self.tree[index]
            index -= index & -index
        return s

AI Coach Hint: The core idea of a Fenwick Tree is the bitwise operation `index & -index`, which isolates the last set bit of `index`. This operation is key to navigating the tree structure and achieving the O(log n) complexity.