What is Segment Tree: Explanation, Example, and Uses

A segment tree is a data structure that stores information about intervals or segments of an array, allowing fast queries and updates on ranges. It helps answer questions like sum, minimum, or maximum over a part of the array efficiently.

How It Works

A segment tree works like a balanced tree where each node represents a segment (or range) of the original array. The root covers the entire array, and each child node covers a smaller part of the array, splitting the range into halves repeatedly.

Think of it like a family tree where each parent node summarizes information about its children. For example, if you want to find the sum of numbers in a range, each node stores the sum of its segment. When you query a range, the tree quickly combines the sums from relevant nodes without checking every element.

This structure allows updates to the array to be reflected quickly in the tree, so queries remain fast even after changes.

Example

This example builds a segment tree for an array and queries the sum of a range.

python

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (2 * self.n)
        # Build the tree by inserting leaves
        for i in range(self.n):
            self.tree[self.n + i] = data[i]
        # Build internal nodes
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, index, value):
        # Set value at position index
        pos = index + self.n
        self.tree[pos] = value
        # Move upward and update parents
        pos //= 2
        while pos > 0:
            self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]
            pos //= 2

    def query(self, left, right):
        # Sum on interval [left, right)
        result = 0
        left += self.n
        right += self.n
        while left < right:
            if left % 2 == 1:
                result += self.tree[left]
                left += 1
            if right % 2 == 1:
                right -= 1
                result += self.tree[right]
            left //= 2
            right //= 2
        return result

# Example usage
arr = [2, 4, 5, 7, 8, 9]
st = SegmentTree(arr)
print(st.query(1, 4))  # Sum from index 1 to 3
st.update(2, 10)       # Update index 2 to 10
print(st.query(1, 4))  # Sum from index 1 to 3 after update

Output

16
21

When to Use

Use a segment tree when you need to perform many queries and updates on intervals of an array efficiently. It is especially useful when queries ask for sums, minimums, maximums, or other combined information over a range.

For example, in gaming leaderboards, you might want to quickly find the highest score in a range of players or update scores frequently. In financial data, you might want to find the total sales in a date range while updating daily sales data.

Key Points

• A segment tree stores information about array segments in a tree structure.
• It allows fast range queries and updates, usually in O(log n) time.
• Each node covers a segment and combines information from child nodes.
• Useful for problems involving intervals like sums, minimums, or maximums.

Key Takeaways

A segment tree efficiently answers range queries and updates on arrays.

It splits the array into segments stored in a balanced tree structure.

Queries and updates run in logarithmic time, much faster than checking all elements.

Ideal for problems needing frequent interval calculations like sums or minimums.