Segment Tree in Data Structure — Operations, Advantages and Disadvantages

A Segment Tree is a binary tree used to store information about intervals (segments) of an array, enabling efficient range queries (such as range sum, minimum, or maximum) and point/range updates.

Structure

Each leaf node represents a single array element, and each internal node represents the combined result (e.g., sum) of its children's ranges. The root represents the entire array's range.

class SegmentTree:
    def __init__(self, arr):
        n = len(arr)
        self.n = n
        self.tree = [0] * (2 * n)
        for i in range(n):
            self.tree[n + i] = arr[i]
        for i in range(n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, index, value):
        i = index + self.n
        self.tree[i] = value
        while i > 1:
            i //= 2
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def range_sum(self, left, right):  # [left, right)
        left += self.n
        right += self.n
        total = 0
        while left < right:
            if left % 2 == 1:
                total += self.tree[left]; left += 1
            if right % 2 == 1:
                right -= 1; total += self.tree[right]
            left //= 2; right //= 2
        return total

Complexity

Advantages

• Efficient range queries and updates in logarithmic time.
• Flexible — can be adapted for sum, min, max, GCD and other associative operations.

Disadvantages

• More complex to implement than simpler structures like prefix sums.
• Uses roughly 2x-4x the memory of the original array.
• Not ideal when the array changes size frequently (rebuilding is costly).

Applications

• Range sum/min/max queries in competitive programming.
• Interval scheduling problems.
• Computational geometry algorithms.