Segment Trees

In the previous lesson, we explored Tries and saw how they enable extremely fast prefix-based searching for strings.

Now we move into a powerful data structure used for range queries and dynamic updates — the Segment Tree.

Segment Trees are widely used in competitive programming, real-time systems, and large-scale analytics engines.

The Problem Segment Trees Solve

Suppose you are given an array of numbers:

[2, 4, 1, 7, 3, 9]

You are asked questions like:

• What is the sum between index 1 and 4?
• What is the minimum value between index 2 and 5?
• Update index 3 to a new value

If we compute answers directly each time, the operations become slow for large arrays.

What Is a Segment Tree?

A Segment Tree is a binary tree where:

Each node represents a range (segment) of the array.

The root represents the entire range, and each leaf represents a single element.

Intermediate nodes store information (sum, min, max, etc.) about their segment.

How the Tree Is Built

The array is recursively divided into two halves.

Each node stores the result of combining its children.

For example, for sum queries, each node stores the sum of its segment.

Why Not Use a Simple Array?

A simple array works well for one-time queries.

But if updates and queries are frequent, the total time becomes too slow.

Segment Trees balance the trade-off between query speed and update speed.

Building a Segment Tree (Sum Example)

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

        build_tree(arr, tree, left, start, mid)
        build_tree(arr, tree, right, mid + 1, end)

        tree[node] = tree[left] + tree[right]

This function builds the tree recursively.

Range Query

To query a range efficiently, we only visit nodes that overlap with the query range.

This avoids scanning the entire array.

def range_sum(tree, node, start, end, l, r):
    if r < start or end < l:
        return 0
    if l <= start and end <= r:
        return tree[node]

    mid = (start + end) // 2
    return (range_sum(tree, 2 * node, start, mid, l, r) +
            range_sum(tree, 2 * node + 1, mid + 1, end, l, r))

Updating a Value

When a value changes, only the nodes covering that index need updates.

This keeps updates efficient.

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

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

Time Complexity

Segment Trees offer:

Query Time: O(log n)
Update Time: O(log n)

This makes them suitable for large-scale applications.

Real-World Applications

Segment Trees are used in:

• Range analytics in databases
• Game leaderboards
• Financial data analysis
• Real-time monitoring systems

Exercises

Quick Quiz

In the next lesson, we will move into Hash Tables and see how constant-time lookups are achieved.