What is a Segment Tree?

A Segment Tree is a tree-based data structure that allows for efficient querying of range-based queries (e.g., sum, minimum, maximum) on an array. It also allows for efficient updates to the array elements. Both query and update operations have a time complexity of O(log n).

What is the difference between a Segment Tree and a Binary Indexed Tree?

Both Segment Trees and Binary Indexed Trees (BITs) are used for range queries and point updates. However, Segment Trees are more versatile and can handle a wider range of queries, such as range minimum/maximum queries, which are not as straightforward with BITs. BITs are generally simpler to implement and have a smaller constant factor in their time complexity.

Data Structures & Algorithms

Segment Tree Interview Questions

Conquer Segment Trees in your coding interviews. Our guide offers detailed explanations, practice problems, and AI-powered feedback to help you master this advanced data structure.

Segment Tree Implementation (Sum Query)

Here is a Python implementation of a Segment Tree that supports range sum queries and point updates.


class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self.data = data
        self._build(1, 0, self.n - 1)

    def _build(self, node, start, end):
        if start == end:
            self.tree[node] = self.data[start]
            return
        mid = (start + end) // 2
        self._build(2 * node, start, mid)
        self._build(2 * node + 1, mid + 1, end)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def update(self, index, value):
        self._update(1, 0, self.n - 1, index, value)

    def _update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
            return
        mid = (start + end) // 2
        if start <= idx <= mid:
            self._update(2 * node, start, mid, idx, val)
        else:
            self._update(2 * node + 1, mid + 1, end, idx, val)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def query(self, l, r):
        return self._query(1, 0, self.n - 1, l, r)

    def _query(self, node, start, end, l, r):
        if r < start or end < l:
            return 0
        if l <= start and end <= r:
            return self.tree[node]
        mid = (start + end) // 2
        p1 = self._query(2 * node, start, mid, l, r)
        p2 = self._query(2 * node + 1, mid + 1, end, l, r)
        return p1 + p2

AI Coach Tip: Segment Trees are powerful but can be tricky to implement correctly. Pay close attention to the array indexing and the recursive structure. Practice with different types of queries (min, max, etc.) to become comfortable with adapting the build, update, and query logic.