Segment Trees and Fenwick Trees Explained

When working with large arrays, repeatedly calculating range sums and handling updates using brute force becomes inefficient. Segment Trees and Fenwick Trees solve this by supporting both range queries and point updates in O(log n) time. These data structures are essential tools for DSA interviews, competitive programming, and high-performance applications. 

Quick TL;DR

• Segment Trees and Fenwick Trees (Binary Indexed Trees) are efficient data structures used for range queries and point updates in O(log n) time.
• Segment Trees offer greater flexibility, supporting various query types and range updates, while Fenwick Trees are simpler, more memory-efficient, and ideal for prefix-sum operations.
• Both are widely used in competitive programming and commonly asked about in technical interviews. 

Want to master segment trees, Fenwick trees, graphs, and all advanced DSA topics with real interview prep and coding projects? Check out HCL GUVI’s Data Structures & Algorithms Programme built for students and professionals who want to crack top product-based company interviews.

What is a Segment Tree?

A segment tree is a binary tree built over an array where each node stores an aggregate value, typically sum, min, or max, for a contiguous segment of the array. The root covers the entire array. Each node splits its range in half: the left child covers the left half, and the right child covers the right half. The leaf nodes each represent a single element.

For an array of n elements, the segment tree has at most 4n nodes and occupies O(n) space. Building it takes O(n log n) time.

Building a Segment Tree

def build(arr, tree, node, start, end):

    if start == end:

        tree[node] = arr[start]   # leaf node

    else:

        mid = (start + end) // 2

        build(arr, tree, 2*node,   start, mid)

        build(arr, tree, 2*node+1, mid+1, end)

        tree[node] = tree[2*node] + tree[2*node+1]

Range Query:O(log n)

def query(tree, node, start, end, l, r):

    if r < start or end < l:          # segment outside range

        return 0

    if l <= start and end <= r:       # segment fully inside range

        return tree[node]

    mid = (start + end) // 2           # partial overlap — go deeper

    left  = query(tree, 2*node,   start, mid,   l, r)

    right = query(tree, 2*node+1, mid+1, end,   l, r)

    return left + right

Point Update: O(log n)

def update(tree, node, start, end, idx, val):

    if start == end:

        tree[node] = val

    else:

        mid = (start + end) // 2

        if idx <= mid:

         update(tree, 2*node,   start, mid,   idx, val)

        else:

         update(tree, 2*node+1, mid+1, end,   idx, val)

        tree[node] = tree[2*node] + tree[2*node+1]

Read More: What is a Tree Data Structure?

Want to master segment trees, Fenwick trees, graphs, and all advanced DSA topics with real interview prep and coding projects? Check out HCL GUVI’s Data Structures & Algorithms Programme built for students and professionals who want to crack top product-based company interviews.

What is a Fenwick Tree (Binary Indexed Tree)?

A Fenwick tree, also called a Binary Indexed Tree (BIT), is a flat array that cleverly uses the binary representation of indices to store partial sums. Each index i in the BIT is responsible for storing the sum of a specific range of elements, determined by the lowest set bit (LSB) of i.

Compared to a segment tree, a Fenwick tree uses less memory (just n+1 integers), has a smaller constant factor, and is faster in practice, but it only natively supports prefix sum queries and point updates. It cannot directly support range min/max queries like a segment tree can.

 Fenwick Tree Update and Prefix Query

class FenwickTree:

    def __init__(self, n):

        self.n = n

        self.tree = [0] * (n + 1)  # 1-indexed

    def update(self, i, delta): # add delta to index i — O(log n)

        while i <= self.n:

         self.tree[i] += delta

         i += i & (-i)      # move to parent using LSB

    def prefix_sum(self, i):   # sum of [1..i] — O(log n)

        total = 0

        while i > 0:

         total += self.tree[i]

         i -= i & (-i)      # move to predecessor using LSB

        return total

    def range_sum(self, l, r): # sum of [l..r] — O(log n)

        return self.prefix_sum(r) - self.prefix_sum(l - 1)

Real-World Use Cases

Both segment trees and Fenwick trees appear in competitive programming, databases, and systems that need efficient range queries over mutable data.

• Stock price range queries: Find the minimum or maximum stock price between two timestamps in O(log n) using a segment tree.
• Frequency tables and rankings: Count inversions in an array, maintain a leaderboard, or compute the rank of a value classic Fenwick tree applications.
• 2D range sum queries: Both trees extend to 2D for image processing, matrix prefix sums, and game maps using a 2D BIT or 2D segment tree.
• Interval scheduling and overlap detection: Segment trees with lazy propagation handle range-mark and range-query operations for booking systems and calendar conflict detection.

Common Mistakes When Working with These Trees

1. Off-by-one errors in indexing: Segment trees typically use 1-based indexing with the tree array sized to 4n. Fenwick trees are always 1-indexed. Mixing 0-based and 1-based indexing within the same implementation is the most common source of wrong answers.

2. Forgetting lazy propagation for range updates: A basic segment tree only supports point updates. If you need to add a value to all elements in a range, you must implement lazy propagation, a deferred update mechanism. Skipping this causes O(n) range updates instead of O(log n).

3. Using a segment tree where a Fenwick tree suffices: For pure prefix sum and point update problems, a Fenwick tree is simpler to implement, uses less memory, and runs faster. Reaching for a segment tree by default adds unnecessary complexity when the problem only requires prefix sums.

Conclusion

Segment trees and Fenwick trees both solve the same core problem: efficient range queries on mutable arrays but with different trade-offs. The segment tree is more powerful, supporting range min/max, range updates with lazy propagation, and arbitrary associative operations. The Fenwick tree is leaner and faster for prefix sum problems, with remarkably concise code once you understand the LSB trick. The best way to learn both is to implement a range sum query from scratch using each structure, then extend your segment tree to support range minimum and finally lazy propagation. 

FAQ

1. What is a segment tree in DSA?

A segment tree is a binary tree built over an array where each node stores an aggregate value sum, min, or max for a contiguous segment. It supports both range queries and point updates in O(log n) time, making it far more efficient than brute-force recomputation for problems with many queries on a mutable array.

2. What is a Fenwick tree (Binary Indexed Tree)?

A Fenwick tree, or Binary Indexed Tree, is a flat array that uses the binary representation of indices to store partial sums efficiently. It supports prefix sum queries and point updates in O(log n) time using simple bit manipulation, with less memory and lower constant factor than a segment tree.

3. What is the difference between a segment tree and a Fenwick tree?

A segment tree is more flexible it supports range min/max queries, range updates with lazy propagation, and arbitrary associative operations. A Fenwick tree is simpler, uses less memory, and is faster in practice but natively supports only prefix sum queries and point updates.

4. What is the time complexity of segment trees and Fenwick trees?

Both data structures support O(log n) range queries and O(log n) point updates. Building a segment tree takes O(n) time; building a Fenwick tree takes O(n log n). A segment tree uses O(4n) space; a Fenwick tree uses O(n) space.

5. What is lazy propagation in a segment tree?

Lazy propagation is a technique that defers range updates in a segment tree. Instead of updating every element in a range immediately, which would cost O(n), the update is stored at the highest relevant node and propagated down only when a child node is actually accessed. This keeps range updates at O(log n).

6. What is the lowest set bit trick in a Fenwick tree?

The lowest set bit (LSB) of an index i, computed as i & (-i), determines which range each BIT position is responsible for. During update, adding the LSB moves you to the next responsible parent.