Segment Trees & Fenwick Trees (Binary Indexed Trees)

Segment Trees

Segment Tree is a binary tree used for storing intervals or segments. Each node of the segment tree stores information about a segment of the array.

It supports efficient range queries and updates with O(log n) time complexity.

Key Operations

• Build: Construct the tree from the input array recursively.
• Query: Find the sum/min/max over a range efficiently.
• Update: Update element values and propagate changes up the tree.

Python Implementation - Range Sum Query & Update

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.build(arr, 0, 0, self.n - 1)
    
    def build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            self.build(arr, 2 * node + 1, start, mid)
            self.build(arr, 2 * node + 2, mid + 1, end)
            self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

    def update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
        else:
            mid = (start + end) // 2
            if idx <= mid:
                self.update(2 * node + 1, start, mid, idx, val)
            else:
                self.update(2 * node + 2, mid + 1, end, idx, val)
            self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

    def query(self, node, start, end, L, R):
        if R < start or L > end:
            return 0
        if L <= start and end <= R:
            return self.tree[node]
        mid = (start + end) // 2
        left_sum = self.query(2 * node + 1, start, mid, L, R)
        right_sum = self.query(2 * node + 2, mid + 1, end, L, R)
        return left_sum + right_sum

# Usage example
arr = [1, 3, 5, 7, 9, 11]
st = SegmentTree(arr)
print("Sum of values in range(1,3):", st.query(0, 0, st.n-1, 1, 3))  # Output: 15
st.update(0, 0, st.n-1, 1, 10)
print("After update sum in range(1,3):", st.query(0, 0, st.n-1, 1, 3))  # Output: 22

Fenwick Trees (Binary Indexed Trees)

Fenwick Tree (or BIT) is a data structure that provides efficient methods for cumulative frequency tables or prefix sums, supporting update and query operations in O(log n) time.

Key Idea

• Uses binary indexed representation of indices.
• Efficiently accumulates sums for prefixes.
• Smaller and simpler than segment tree for prefix sum problems.

Python Implementation - Prefix Sum & Update

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

    def update(self, idx, val):
        while idx <= self.size:
            self.tree[idx] += val
            idx += idx & (-idx)

    def query(self, idx):
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= idx & (-idx)
        return res

# Usage example
arr = [1, 3, 5, 7, 9, 11]
ft = FenwickTree(len(arr))
for i, val in enumerate(arr, 1):
    ft.update(i, val)

print("Sum of first 3 elements:", ft.query(3))  # Output: 9 (1+3+5)
ft.update(2, 4)  # Increment value at index 2 by 4
print("After update, sum of first 3 elements:", ft.query(3))  # Output: 13 (1+7+5)