DSA — Segment Tree

What is a Segment Tree?

A binary tree for storing ranges of data, supporting efficient range queries and updates.

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self.build(data, 1, 0, self.n - 1)
    
    def build(self, data, node, start, end):
        if start == end:
            self.tree[node] = data[start]
        else:
            mid = (start + end) // 2
            self.build(data, 2 * node, start, mid)
            self.build(data, 2 * node + 1, mid + 1, end)
            self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

Range Query

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
    left_sum = self.query(2 * node, start, mid, l, r)
    right_sum = self.query(2 * node + 1, mid + 1, end, l, r)
    return left_sum + right_sum

Update

def update(self, node, start, end, idx, val):
    if start == end:
        self.tree[node] = val
    else:
        mid = (start + end) // 2
        if 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]

Time Complexity

Operation	Complexity
Build	O(n)
Query	O(log n)
Update	O(log n)

Applications

• Range sum queries
• Range minimum/maximum
• Range updates
• Inversion counting

Mini Practice

1. Build a segment tree
2. Implement range query
3. Update values
4. Solve range problem

Up Next

Continue with Fenwick Tree — binary indexed tree.