No history yet

Segment Tree Basics

The Problem with Ranges

Imagine you have a list of numbers, like daily sales figures for a month. A common task is to find the total sales over a specific period, say, from the 5th to the 15th of the month. The straightforward way is to loop through the numbers from the 5th to the 15th and add them up. This works fine for one or two queries.

But what if you need to do this thousands of times for different date ranges? Adding up numbers repeatedly becomes slow. If your array has NN elements, each sum query takes, on average, a time proportional to NN. If you have QQ queries, the total time is roughly Q×NQ \times N. This can get out of hand quickly.

We need a smarter way to handle these "range queries."

Enter the Segment Tree

A segment tree is a data structure designed specifically for this problem. It pre-processes the array to answer range queries very quickly. Think of it like a company's organizational chart for summarizing data. The CEO at the top knows the total sales for the entire company. The vice presidents below know the sales for their respective divisions (e.g., North America and Europe). Under them, regional managers know the sales for their specific regions, and so on, down to individual salespeople.

A segment tree does the same for an array. It's a binary tree where each node represents a range, or "segment," of the original array. The root node represents the entire array. Its two children represent the left and right halves of the array. This splitting continues until we reach the leaf nodes, which each represent a single element from the original array.

Each node in the tree stores a pre-computed value for its range, such as the sum, minimum, or maximum value.

Building and Using the Tree

The tree is built from the bottom up. We start with the individual elements in the leaf nodes. Then, we move up, calculating the value for each parent node by combining the values of its children. For a sum segment tree, a parent's value is simply the sum of its left and right children's values. This process continues until we reach the root.

Once the tree is built, querying is fast. To find the sum of a range, like A[2] to A[6], we traverse the tree. We find the nodes that perfectly cover our query range without overlapping. Instead of adding five individual elements, we might just need to add the sums from two or three pre-computed nodes in the tree. For example, we could combine the sum for the range [2-3], the element at [4], and the range [5-6].

This is much more efficient. For an array of size NN, both building the tree and performing a query take O(log⁡N)O(\log N) time. This is a massive improvement over the O(N)O(N) time per query of the simple loop.

# Let's say we have our array A
A = [2, 5, 1, 4, 9, 3, 7, 6]

# The segment tree is often stored in an array as well.
# For an array of size n, the tree will need about 4n space.
# Let's call it 'tree'.

# Simplified query function logic
def query(node, start, end, range_start, range_end):
    # If the node's range is completely outside our query range
    if range_start > end or range_end < start:
        return 0 # Return a neutral value

    # If the node's range is completely inside our query range
    if range_start <= start and end <= range_end:
        return tree[node] # Return the pre-computed sum

    # If the ranges partially overlap, check children
    mid = (start + end) // 2
    left_sum = query(2 * node + 1, start, mid, range_start, range_end)
    right_sum = query(2 * node + 2, mid + 1, end, range_start, range_end)
    
    return left_sum + right_sum

# To get sum for A[2] to A[6], we would call:
# query(0, 0, len(A)-1, 2, 6)
# The function would recursively find the nodes that cover this range.

The power of the segment tree comes from its divide-and-conquer approach. By breaking the problem into smaller, pre-solved pieces, it can answer questions about large sections of data with very little work.

Quiz Questions 1/5

Using a simple loop to calculate the sum of a range of elements in an array of size NN has a time complexity of:

Quiz Questions 2/5

In a segment tree built over an array, what does the root node represent?

This covers the fundamental structure and purpose of a segment tree. It provides a powerful foundation for handling range-based problems efficiently.