DSA Segment Trees

A segment tree is a tree that stores information about ranges of a list. Each node holds a summary, such as a sum, a minimum, or a maximum, for one section of the list. The structure answers range questions and applies updates, both in O(log n) time.

Think about a school with 8 classrooms. The principal wants the total number of students in classrooms 3 to 6 at any time, and student counts change daily. Recounting every room is slow. A segment tree keeps subtotals for pairs of rooms, groups of four rooms, and all rooms together. A query adds only a few subtotals, and an update refreshes only a few of them.

Why Not a Prefix Sum

A prefix sum answers range questions in O(1) time but needs O(n) time to rebuild after any change. A plain loop updates in O(1) time but needs O(n) time per query. A segment tree balances both costs at O(log n), which works well when updates and queries mix.

Structure

The leaves hold the original items. Each parent holds the sum of its two children. The root holds the total.

List: [2, 1, 5, 3]

              [0..3] = 11
             /           \
       [0..1] = 3     [2..3] = 8
        /      \       /      \
   [0]=2     [1]=1  [2]=5     [3]=3

Array-Based Implementation

A compact version stores the tree in one list of size 2n. The leaves sit in positions n to 2n - 1. The parent of position i sits at i // 2. The children of position i sit at 2i and 2i + 1.

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (2 * self.n)
        for i in range(self.n):
            self.tree[self.n + i] = data[i]
        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):
        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 query(self, left, right):
        # sum of items from left up to, but not including, right
        result = 0
        l = left + self.n
        r = right + self.n
        while l < r:
            if l % 2 == 1:
                result += self.tree[l]
                l += 1
            if r % 2 == 1:
                r -= 1
                result += self.tree[r]
            l //= 2
            r //= 2
        return result

Using the Tree

st = SegmentTree([2, 1, 5, 3])
print(st.query(1, 3))   # 6   (1 + 5)
st.update(2, 10)        # the 5 becomes 10
print(st.query(1, 3))   # 11  (1 + 10)
print(st.query(0, 4))   # 16  (whole list)

Before update               After update

      11                          16
     /  \                        /  \
    3    8                      3    13
   / \  / \                    / \   / \
  2  1 5   3                  2  1 10   3

An update touches one leaf and its ancestors only. A list of one million items needs about 20 steps.

Other Questions the Tree Can Answer

Swapping the sum for another combining rule changes the question. Storing the smaller of two children answers range minimum queries. Storing the larger answers range maximum queries. The combining rule must work the same no matter how the range splits, which excludes operations where grouping changes the result.

Real-Life Uses

Game servers track live scores across ranges of players. Stock tools find the highest price in any date range while new prices arrive. Mapping tools count points inside rectangular regions. Competitive programming problems use segment trees heavily for range queries with updates.

Segment Tree vs Fenwick Tree

A Fenwick tree, known as a binary indexed tree, solves prefix sum queries with updates using less code and less memory. A segment tree handles more kinds of questions, such as minimums, maximums, and custom rules. Start with a segment tree for flexibility, and switch to a Fenwick tree when the problem asks only for sums and speed of coding matters.

Practice Ideas

Build a tree over the list [5, 3, 8, 6, 2, 7] and answer three range sums by hand. Update one value and redo the queries. Change the combining rule to take the smaller of two children and repeat the exercise to see how one structure serves many questions.

Common Mistakes

Mixing inclusive and exclusive range ends causes off-by-one answers. This version treats the right end as exclusive. Forgetting to rebuild the parents after an update leaves stale totals. Using a size smaller than 2n breaks the layout. Test small lists and compare with a plain sum loop.

Complexity Summary

• Build: O(n)
• Query: O(log n)
• Update: O(log n)
• Space: O(n)

Key Points

• A segment tree stores summaries of list sections.
• Leaves hold the items, and parents combine their children.
• Queries and updates both run in O(log n) time.
• The same shape handles sums, minimums, and maximums.
• The structure suits data that changes while queries keep arriving.