Segment Tree: Range Query Data Structure Explained with Examples

Segment Tree is a specialized data structure used for answering range queries and performing updates on arrays efficiently. Whether you want to compute the sum, minimum, or maximum of elements in a subarray, a Segment Tree provides a way to achieve log-time complexity for both query and update operations. This makes it extremely popular in competitive programming, optimization problems, and real-time applications where multiple queries need to be processed quickly.

Table of Contents

Why Segment Tree?

Suppose you have an array of integers and need to perform multiple range queries, such as finding the sum of all elements between index l and r. A naive approach would take O(n) time per query. With Segment Tree, these queries can be answered in O(log n) time, and even if the array changes (updates), the Segment Tree can update values in O(log n) time.

Segment Tree Structure

The Segment Tree is essentially a binary tree where:

Each node represents an interval (or segment) of the array.
The root represents the entire array.
Each internal node represents the union of its two children segments.
Leaf nodes represent single array elements.

Building a Segment Tree

Building the tree requires recursively dividing the array into halves until each segment represents one element. The build operation runs in O(n) time.


def build_tree(arr, tree, node, start, end):
    if start == end:
        # Leaf node
        tree[node] = arr[start]
    else:
        mid = (start + end) // 2
        build_tree(arr, tree, 2*node, start, mid)
        build_tree(arr, tree, 2*node+1, mid+1, end)
        tree[node] = tree[2*node] + tree[2*node+1]

Example: Building from Array [1, 3, 5, 7, 9, 11]

This array produces the following Segment Tree for sum queries:

Every parent is the sum of its children, giving both the breakdown of smaller ranges and the whole array.

Range Query with Segment Tree

Once built, we can answer queries like sum of elements between two indices in O(log n) using traversal.


def range_query(tree, node, start, end, l, r):
    if r < start or end < l:
        return 0  # outside range
    if l <= start and end <= r:
        return tree[node]  # segment completely inside
    mid = (start + end) // 2
    left_sum = range_query(tree, 2*node, start, mid, l, r)
    right_sum = range_query(tree, 2*node+1, mid+1, end, l, r)
    return left_sum + right_sum

Example query: sum of elements between index 1 and 3 in array [1, 3, 5, 7, 9, 11].

The highlighted query path shows accessing nodes covering [1,3], giving the result 15.

Updating a Value

With Segment Tree, updating a single array element automatically updates its parent nodes in O(log n).


def update_tree(arr, tree, node, start, end, idx, val):
    if start == end:
        arr[idx] = val
        tree[node] = val
    else:
        mid = (start + end) // 2
        if start <= idx and idx <= mid:
            update_tree(arr, tree, 2*node, start, mid, idx, val)
        else:
            update_tree(arr, tree, 2*node+1, mid+1, end, idx, val)
        tree[node] = tree[2*node] + tree[2*node+1]

Applications of Segment Tree

Range Sum Queries: Quickly find sums of subarrays.
Range Minimum/Maximum: Adapt Segment Tree logic for min/max queries.
Dynamic Updates: Efficiently handle updates in datasets like stock prices.
Competitive Programming: Often used for interval problems with constraints.

Interactive Visualization Idea

To better understand Segment Trees, try implementing an interactive playground where inputting an array dynamically builds the Segment Tree and allows users to test queries. For instance, sliders can control the query range [L, R] while the visual tree highlights the nodes used to compute the query result.

Complexities

Building: O(n)
Query: O(log n)
Update: O(log n)
Memory: Around 4n for array-based tree representation

Conclusion

The Segment Tree is a highly effective data structure for handling range query problems with updates. It strikes an ideal balance of speed and flexibility and is an essential tool for programmers dealing with intervals and dynamic data. By mastering Segment Trees, you’ll gain a fundamental skill that will serve you well in algorithmic problem-solving and competitive programming.