Fenwick Trees vs. Segment Trees: A Comparative Guide

What Are Fenwick Trees and Segment Trees?

Fenwick Trees (Binary Indexed Trees)

A Fenwick Tree is a compact data structure used for:

• Calculating prefix sums.
• Handling point updates in logarithmic time.

Fenwick Trees are ideal for scenarios with frequent updates and prefix queries, but they don’t handle full range modifications as efficiently.

Segment Trees

A Segment Tree is a binary tree-like structure designed to handle:

• Range queries (e.g., sum, min, max).
• Range updates (lazy propagation).

Segment Trees can handle more complex problems but are larger and more intricate to implement.

Comparison of Features:

• Fenwick Tree
• Space Complexity: O(n)
• Update Complexity: O(log⁡ n)
• Query Complexity: O(log n) (prefix only)
• Range Updates: Not supported
• Ease of Implementation: Simple
• Segment Tree
• Space Complexity: O(2n−1) (~O(4n) for lazy propagation)
• Update Complexity: O(log⁡ n)
• Query Complexity: O(log n) (range queries supported)
• Range Updates: Supported (with lazy propagation)
• Ease of Implementation: Moderate

Fenwick Tree: Implementation

Key Operations

1. Update: Add a value to a specific index.
2. Query: Compute the prefix sum up to a given index.

Python Code Example

Here’s a simple Fenwick Tree for prefix sum queries:

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)  # 1-indexed
    
    def update(self, index, value):
        """Add `value` to index `index`."""
        while index <= self.size:
            self.tree[index] += value
            index += index & -index  # Move to next responsible index
    
    def query(self, index):
        """Compute the prefix sum up to `index`."""
        sum = 0
        while index > 0:
            sum += self.tree[index]
            index -= index & -index  # Move to parent index
        return sum

# Example Usage
ft = FenwickTree(10)
ft.update(3, 5)  # Add 5 at index 3
print(ft.query(3))  # Output: 5
ft.update(5, 10)  # Add 10 at index 5
print(ft.query(5))  # Output: 15

Segment Tree: Implementation

Key Operations

1. Build: Construct the tree from an array.
2. Query: Compute the result for a range.
3. Update: Modify the value at a specific index.
4. Lazy Propagation: Efficiently update a range.

Python Code Example

Here’s a Segment Tree for range sum queries:

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)  # Allocate enough space
        self.build(arr, 0, 0, self.n - 1)

    def build(self, arr, node, start, end):
        """Recursively build the segment tree."""
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            left_child = 2 * node + 1
            right_child = 2 * node + 2
            self.build(arr, left_child, start, mid)
            self.build(arr, right_child, mid + 1, end)
            self.tree[node] = self.tree[left_child] + self.tree[right_child]

    def query(self, node, start, end, l, r):
        """Query the sum in range [l, r]."""
        if r < start or l > end:  # Out of range
            return 0
        if l <= start and end <= r:  # Completely within range
            return self.tree[node]
        mid = (start + end) // 2
        left_child = 2 * node + 1
        right_child = 2 * node + 2
        left_sum = self.query(left_child, start, mid, l, r)
        right_sum = self.query(right_child, mid + 1, end, l, r)
        return left_sum + right_sum

    def update(self, node, start, end, idx, value):
        """Update the value at index `idx`."""
        if start == end:
            self.tree[node] = value
        else:
            mid = (start + end) // 2
            left_child = 2 * node + 1
            right_child = 2 * node + 2
            if start <= idx <= mid:
                self.update(left_child, start, mid, idx, value)
            else:
                self.update(right_child, mid + 1, end, idx, value)
            self.tree[node] = self.tree[left_child] + self.tree[right_child]

# Example Usage
arr = [1, 2, 3, 4, 5]
st = SegmentTree(arr)
print(st.query(0, 0, len(arr) - 1, 1, 3))  # Sum of range [1, 3]
st.update(0, 0, len(arr) - 1, 2, 10)  # Update index 2 to 10
print(st.query(0, 0, len(arr) - 1, 1, 3))  # Updated sum of range [1, 3]

When to Use Which?

1. Use Fenwick Tree if:

• You only need prefix sums or simple range operations.
• Memory constraints are tight.
• Simplicity is a priority.

1. Use Segment Tree if:

• You need to support complex range queries (e.g., min, max).
• Frequent range updates are required.
• You want flexibility to handle various aggregate functions.

Conclusion

Both Fenwick Trees and Segment Trees are powerful tools in your algorithmic arsenal.

Fenwick Trees shine in simplicity and efficiency for specific tasks, while Segment Trees offer flexibility for more complex operations.

Choose wisely based on your problem requirements.

Further Reading and Challenges

• Dive deeper into lazy propagation for Segment Trees.
• Explore 2D Fenwick Trees for matrix operations.
• Implement both structures for real-world datasets and compare performance.

Happy coding! 🚀