Fenwick Tree: Prefix Sums and Point Updates

1. The Problem, Re-examined

Let's quickly revisit the core problem: we have an array of numbers and need to perform two operations very frequently:

1. prefix_sum(k): Calculate the sum of elements from the start of the array up to index k.
2. update(k, delta): Add a delta to the element at index k.

As we discussed, a simple array is fast for updates (O(1)) but slow for queries (O(n)). A prefix sum array is the reverse: fast for queries (O(1)) but slow for updates (O(n)). Both Segment Trees and Fenwick Trees strike a balance, achieving O(log n) for both operations. The Fenwick Tree does so with less space and often simpler code.

2. The Core Idea: Clever Partial Sums

Instead of storing sums for every possible prefix, a Fenwick Tree stores partial sums in a way that cleverly maps to the binary representation of array indices.

Technical Explanation

A Fenwick Tree is an array (let's call it bit_array) of the same size as the input array (plus one, for 1-based indexing). Each index i in bit_array is "responsible" for storing the sum of a specific range of elements from the original array. The size of this range is determined by the least significant bit (LSB) of the index i.

Specifically, bit_array[i] stores the sum of elements from the original array in the range [i - (LSB(i)) + 1, i].

Metaphor: Express Checkout Lanes

Imagine you need to sum the first 13 items in a shopping cart.

• Naive approach: Add them one by one (1+1+1+...+1, 13 steps).
• Fenwick Tree approach: The number 13 in binary is 1101, which is 8 + 4 + 1. The Fenwick Tree allows you to do this:
  1. Grab the pre-calculated sum of the last 1 item (from index 13 to 13).
  2. Jump back and grab the pre-calculated sum of the next 4 items (from index 9 to 12).
  3. Jump back again and grab the pre-calculated sum of the next 8 items (from index 1 to 8).

You get the total sum in just 3 steps (log n complexity) instead of 13 (n complexity) by using these pre-computed "blocks" whose sizes are powers of two.

The magic that allows us to find the size of these blocks and navigate between them is bit manipulation.

3. Bit Manipulation: The Engine Room

The core of the Fenwick Tree's efficiency comes from a single, powerful bitwise trick to isolate the least significant bit (LSB). For any positive integer i, the value of its LSB can be found with:

Under the Hood: Two's Complement

This works because of how computers store negative numbers using two's complement. To get -i from i:

1. Invert all the bits of i (~i).
2. Add 1.

When you add 1, it flips all the trailing 0s to 1s and flips the rightmost 1 to a 0. When you then perform a bitwise AND between i and -i, the only bit that remains a 1 in both numbers is that original rightmost 1.

Example: i = 12

• Binary of 12: ...00001100
• Invert the bits: ...11110011
• Add 1 (gives -12): ...11110100
• i & -i:

    00001100  (12)
  & 11110100  (-12)
  ----------------
    00000100  (4)
  

The result, 4, is the value of the least significant bit of 12. This tells us that bit_array[12] is responsible for a range of size 4.

4. Implementing the Operations

With this bitwise trick, the update and query operations become remarkably simple.

prefix_sum(i): Moving to the "Parent"

To get the sum up to index i, we start at i and keep jumping to the "parent" of the current range until we reach the beginning. The parent is found by turning off the LSB.

Algorithm:

1. Initialize sum = 0.
2. Start at index = i.
3. While index > 0:
   a. Add bit_array[index] to sum.
   b. Move to the next index by subtracting the LSB: index -= index & -i.
4. Return sum.

This traverse is O(log n) because we turn off one set bit in each step.

update(i, delta): Notifying "Ancestors"

When we update a value at a given index in the original array, we must update all ranges in the Fenwick Tree that include this index. These are the "ancestors" in the tree structure. We find the next ancestor by adding the LSB.

Algorithm:

1. Start at index = i.
2. While index is within the array bounds:
   a. Add delta to bit_array[index].
   b. Move to the next responsible index by adding the LSB: index += index & -i.

This is also an O(log n) operation.

5. Full Python Implementation

Here is a complete implementation. We'll use 1-based indexing internally for the bit_array to make the bitwise logic work as described. Our public-facing methods will still accept standard 0-based indices and handle the conversion.

class FenwickTree:
    """
    Fenwick Tree (Binary Indexed Tree) for prefix sums and point updates.
    """
    def __init__(self, nums: list[int]):
        """
        Initializes the Fenwick Tree.
        The naive O(n log n) build is used for simplicity.
        """
        self.n = len(nums)
        # We use a 1-based array for the BIT, so size is n+1
        self.bit_array = [0] * (self.n + 1)
        
        # Populate the tree by updating each element
        for i, num in enumerate(nums):
            self.update(i, num)

    def _update_internal(self, index: int, delta: int):
        """Internal update method using 1-based indexing."""
        index += 1  # Convert to 1-based index
        while index <= self.n:
            self.bit_array[index] += delta
            # Move to the next responsible index
            index += index & -index

    def update(self, index: int, val: int):
        """
        Updates the value at a 0-based index to a new value.
        This is not a delta update, but a value replacement.
        This requires calculating the delta from the old value.
        
        For a more direct 'add' functionality, one would need to store
        the original array or implement a 'get' method. A simpler API
        is often just to provide an 'add' or 'increment' function.
        Let's stick to the core logic and implement 'add'.
        """
        raise NotImplementedError("This simplified example focuses on `add`. A full `update` requires tracking original values.")

    def add(self, index: int, delta: int):
        """
        Adds a delta to the value at a 0-based index.
        """
        self._update_internal(index, delta)

    def prefix_sum(self, index: int) -> int:
        """
        Calculates the prefix sum up to a 0-based index (inclusive).
        """
        index += 1  # Convert to 1-based index
        result = 0
        while index > 0:
            result += self.bit_array[index]
            # Move to the parent in the implicit tree
            index -= index & -index
        return result

    def range_sum(self, left: int, right: int) -> int:
        """
        Calculates the sum of a 0-based range [left, right] (inclusive).
        """
        if left > right:
            return 0
        if left == 0:
            return self.prefix_sum(right)
        return self.prefix_sum(right) - self.prefix_sum(left - 1)

# Let's adjust the __init__ to use the public 'add' method
class FenwickTree:
    def __init__(self, size: int):
        self.n = size
        self.bit_array = [0] * (self.n + 1)

    # ... (add, prefix_sum, range_sum methods as above) ...

# Example Usage:
nums = [1, 3, 5, 7, 9, 11]
ft = FenwickTree(len(nums))

# Build the tree
for i, num in enumerate(nums):
    ft.add(i, num)

# Query the sum of range [1, 3] (3 + 5 + 7)
print(f"Sum of range [1, 3]: {ft.range_sum(1, 3)}") # Expected: 15

# Add 1 to the element at index 2 (5 becomes 6)
ft.add(2, 1)

# Query the sum of range [1, 3] again (3 + 6 + 7)
print(f"Sum of range [1, 3] after update: {ft.range_sum(1, 3)}") # Expected: 16

6. Trade-offs: Fenwick Tree vs. Segment Tree

The Fenwick Tree is not a universal replacement for the Segment Tree. It's crucial to know when to use each.

When to choose a Fenwick Tree:

• You need fast prefix sum queries and point updates.
• Memory is a significant concern.
• Implementation speed and simplicity are valued (e.g., in a coding interview or contest).

When to choose a Segment Tree:

• You need to query for range minimum/maximum or other non-invertible operations.
• You need to perform range updates (e.g., "add 5 to all elements from index i to j").

Conclusion

You've now mastered the Fenwick Tree, an incredibly clever and efficient data structure. Its elegance lies in leveraging the binary representation of indices to achieve logarithmic performance for both prefix sum queries and point updates, all while maintaining a minimal memory footprint.

Key Takeaways:

• Core Purpose: A specialized data structure for O(log n) prefix sum queries and point updates.
• Key Mechanic: It relies on bit manipulation, specifically the i & -i trick, to navigate an implicit tree structure represented in a single array.
• Trade-offs: It is more space-efficient and often simpler to code than a Segment Tree, but less flexible in the types of queries it can handle.
• Indexing: The underlying logic relies on 1-based indexing.

Preview of the Next Lesson:
We've spent the last two lessons on data structures for numeric aggregation. Now, we'll shift our focus to string-related problems. In the next lesson, we will explore and contrast two fundamental structures for prefix-based string searches: Tries and Hash Tables. We'll analyze their performance, memory usage, and ideal use cases, such as implementing an autocomplete feature.