Segment Trees and Fenwick Trees: Range Query Masters

Introduction

Imagine you’re building an application that tracks stock prices. Users need to query the maximum price over a date range, the total trading volume between two dates, or find the first day when prices exceeded a threshold. Each query needs to be fast, and the data changes frequently.

This is a classic problem where segment trees and Fenwick trees (also called Binary Indexed Trees) shine. These data structures allow you to process range queries and point updates in O(log n) time, making them indispensable for many real-world applications.

This article explores both data structures, explaining when to use each and how they achieve their remarkable performance.

The Range Query Problem

Given an array, you often need to answer questions about subarrays:

What is the sum of elements from index L to R?
What is the maximum or minimum value in a range?
How many elements are greater than X in a range?
What is the first position where cumulative sum exceeds X?

Naive approaches either precompute all possible answers (O(n²) space, impractical) or compute each query from scratch (O(n) per query, too slow for large datasets).

We need a data structure that supports:

Point updates: Change a single element
Range queries: Answer questions about subarrays

Both operations should be fast—ideally O(log n).

Introducing Segment Trees

A segment tree is a binary tree where each node represents a segment (range) of the array. The root represents the entire array, and each leaf represents a single element. Internal nodes represent the union of their children’s ranges.

For an array of size n, the segment tree uses approximately 4n space and has height O(log n).

Building the tree: Start with leaves representing single elements. Then build upward—each internal node combines its children’s information (sum, max, min, etc.).

Querying a range: To find the answer for range [L, R], you traverse the tree. When a node’s range is completely outside your query, skip it. When completely inside, use the node’s precomputed value. When partially overlapping, recurse into children and combine results.

Updating a value: Change a leaf, then recalculate values going up to the root. This takes O(log n) time.

What Can Segment Trees Store?

The power of segment trees comes from their flexibility. Each node can store any associative information about its range:

Sum: Range sum queries (most common)
Minimum/Maximum: Range minimum/maximum queries
Count: Number of elements satisfying a condition
GCD/LCM: Range GCD or LCM queries
Custom: Any operation that can be combined from smaller ranges

This makes segment trees incredibly versatile for different problem types.

Fenwick Trees: The Space-Efficient Alternative

Also known as Binary Indexed Trees (BIT), Fenwick trees provide the same functionality as segment trees but with less memory. They use O(n) space instead of O(4n).

The clever insight behind Fenwick trees is that we don’t need to store explicit tree structure. Instead, we use an array where each position stores the sum of a specific range. This is achieved through binary representation of indices.

How it works:

Each index i stores the sum of elements in a range whose length equals the lowest set bit of i. For example:

Index 1 (binary 001) stores element 1
Index 2 (binary 010) stores elements 1-2
Index 4 (binary 100) stores elements 1-4
Index 6 (binary 110) stores elements 5-6

Prefix sum: To get the sum from index 1 to i, you use a bit manipulation trick that walks through relevant indices in O(log n) time.

Range sum: To get sum [L, R], compute prefix(R) - prefix(L-1).

Point update: Update an index and all “responsible” ancestors in O(log n).

Segment Trees vs Fenwick Trees

When should you use which?

Feature	Segment Tree	Fenwick Tree
Space	O(4n)	O(n)
Range Maximum/Minimum	Yes	Limited
Range Sum	Yes	Yes
Flexible operations	Yes	No
Implementation	More complex	Simpler

Use Fenwick trees when: You only need range sums, space is important, and you want simpler code.

Use segment trees when: You need different operations (min, max, custom), or when you need to query complex properties of ranges.

Practical Applications

These data structures appear in many real applications:

Competitive programming: Essential for problems involving range queries with updates.

Statistical analysis: Computing running statistics, moving averages, quantiles.

Image processing: Efficient convolution and filtering operations.

Database indexing: Underlying many index structures.

Network routing: Maintaining routing tables with frequent updates.

Implementing a Fenwick Tree

Here’s a basic implementation in Python:

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)
    
    def update(self, i, delta):
        while i <= self.n:
            self.bit[i] += delta
            i += i & (-i)
    
    def query(self, i):
        result = 0
        while i > 0:
            result += self.bit[i]
            i -= i & (-i)
        return result
    
    def range_sum(self, l, r):
        return self.query(r) - self.query(l - 1)

The beauty is in the bit manipulation—i & (-i) gives the lowest set bit, which determines the “jump” to the next relevant index.

Advanced Variations

Lazy propagation segment trees: When you need to update ranges (add X to all elements in [L, R]) instead of just point updates, lazy propagation stores pending operations and applies them only when necessary.

Persistent segment trees: Maintain version history of the tree, allowing you to query historical states efficiently.

2D segment trees: For matrix queries, extending the concept to two dimensions.

External Resources

Conclusion

Segment trees and Fenwick trees are essential tools for any programmer dealing with range queries. They transform O(n) operations into O(log n), making previously impossible problems tractable.

The key is choosing the right tool: Fenwick trees for simple range sums where space matters, segment trees for complex queries or different operations. Both are worth knowing and frequently appear in technical interviews and real-world applications.