Skip to content
Codeloom
DSA

Segment Trees Explained

Master segment trees for range queries and updates. Covers build, query, update, lazy propagation, and applications for range sum, min, and max problems.

·10 min read · By Codeloom
Advanced 16 min read

What you'll learn

  • ✓What segment trees are and when to use them
  • ✓How to build, query, and update a segment tree
  • ✓How lazy propagation enables efficient range updates
  • ✓How to adapt segment trees for sum, min, and max queries
  • ✓Common competitive programming patterns

Prerequisites

  • •Arrays and recursion
  • •Binary trees
  • •Big-O analysis

A segment tree is a binary tree that stores information about intervals (segments) of an array. Each node covers a range of indices and stores an aggregate value for that range. This structure supports both range queries and point updates in O(log n) time, compared to O(n) for a naive approach.

Why segment trees

Consider an array of n integers. You need to answer two types of operations repeatedly:

  1. Query: What is the sum of elements from index l to r?
  2. Update: Change the value at index i to v.
ApproachQueryUpdate
Naive arrayO(n)O(1)
Prefix sumO(1)O(n)
Segment treeO(log n)O(log n)

When you have a mix of many queries and updates, the segment tree wins.

Building a segment tree

The tree is stored in a flat array of size 4n. Node at index i has children at 2i and 2i+1.

class SegmentTree:
    def __init__(self, arr: list[int]):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self._build(arr, 1, 0, self.n - 1)
    
    def _build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
            return
        
        mid = (start + end) // 2
        self._build(arr, 2 * node, start, mid)
        self._build(arr, 2 * node + 1, mid + 1, end)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

For the array [1, 3, 5, 7, 9, 11], the segment tree looks like:

              36 [0,5]
            /          \
       9 [0,2]        27 [3,5]
       /    \          /    \
    4 [0,1]  5[2,2]  16[3,4] 11[5,5]
    /   \              /   \
  1[0] 3[1]         7[3] 9[4]

Range query

To query the sum from index l to r:

class SegmentTree:
    # ... __init__ and _build from above ...
    
    def query(self, l: int, r: int) -> int:
        """Return the sum of elements from index l to r (inclusive)."""
        return self._query(1, 0, self.n - 1, l, r)
    
    def _query(self, node, start, end, l, r):
        # no overlap
        if r < start or end < l:
            return 0
        
        # complete overlap
        if l <= start and end <= r:
            return self.tree[node]
        
        # partial overlap
        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
arr = [1, 3, 5, 7, 9, 11]
st = SegmentTree(arr)

print(st.query(1, 3))  # 3 + 5 + 7 = 15
print(st.query(0, 5))  # 1 + 3 + 5 + 7 + 9 + 11 = 36
print(st.query(2, 4))  # 5 + 7 + 9 = 21

Point update

To change a single element:

class SegmentTree:
    # ... previous methods ...
    
    def update(self, idx: int, val: int) -> None:
        """Set arr[idx] = val and update the tree."""
        self._update(1, 0, self.n - 1, idx, val)
    
    def _update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
            return
        
        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]
st = SegmentTree([1, 3, 5, 7, 9, 11])
print(st.query(0, 5))  # 36

st.update(2, 10)        # change 5 -> 10
print(st.query(0, 5))  # 41
print(st.query(1, 3))  # 3 + 10 + 7 = 20

Complete implementation

Putting it all together:

class SegmentTree:
    def __init__(self, arr: list[int]):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        if self.n > 0:
            self._build(arr, 1, 0, self.n - 1)
    
    def _build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
            return
        mid = (start + end) // 2
        self._build(arr, 2 * node, start, mid)
        self._build(arr, 2 * node + 1, mid + 1, end)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def query(self, l: int, r: int) -> int:
        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
        return (self._query(2 * node, start, mid, l, r) +
                self._query(2 * node + 1, mid + 1, end, l, r))
    
    def update(self, idx: int, val: int) -> None:
        self._update(1, 0, self.n - 1, idx, val)
    
    def _update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
            return
        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]

Lazy propagation

What if you need to update an entire range, not just a single element? For example, “add 5 to all elements from index 2 to 8.” Without lazy propagation, this takes O(n log n). With it, O(log n).

The idea: when updating a range, do not recurse all the way down. Instead, mark the node as “pending” and push the update down only when needed.

class LazySegmentTree:
    def __init__(self, arr: list[int]):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)
        if self.n > 0:
            self._build(arr, 1, 0, self.n - 1)
    
    def _build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
            return
        mid = (start + end) // 2
        self._build(arr, 2 * node, start, mid)
        self._build(arr, 2 * node + 1, mid + 1, end)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def _push_down(self, node, start, end):
        """Push pending updates to children."""
        if self.lazy[node] != 0:
            mid = (start + end) // 2
            self._apply(2 * node, start, mid, self.lazy[node])
            self._apply(2 * node + 1, mid + 1, end, self.lazy[node])
            self.lazy[node] = 0
    
    def _apply(self, node, start, end, val):
        """Apply an update to a node."""
        self.tree[node] += val * (end - start + 1)
        self.lazy[node] += val
    
    def range_update(self, l: int, r: int, val: int) -> None:
        """Add val to all elements from index l to r."""
        self._range_update(1, 0, self.n - 1, l, r, val)
    
    def _range_update(self, node, start, end, l, r, val):
        if r < start or end < l:
            return
        if l <= start and end <= r:
            self._apply(node, start, end, val)
            return
        self._push_down(node, start, end)
        mid = (start + end) // 2
        self._range_update(2 * node, start, mid, l, r, val)
        self._range_update(2 * node + 1, mid + 1, end, l, r, val)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def query(self, l: int, r: int) -> int:
        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]
        self._push_down(node, start, end)
        mid = (start + end) // 2
        return (self._query(2 * node, start, mid, l, r) +
                self._query(2 * node + 1, mid + 1, end, l, r))
arr = [1, 3, 5, 7, 9, 11]
lst = LazySegmentTree(arr)

print(lst.query(0, 5))      # 36

lst.range_update(1, 4, 10)  # add 10 to indices 1-4
# array is now [1, 13, 15, 17, 19, 11]
print(lst.query(0, 5))      # 76
print(lst.query(1, 4))      # 13 + 15 + 17 + 19 = 64

Min/Max segment tree

Changing the aggregate function from sum to min or max is straightforward:

class MinSegmentTree:
    def __init__(self, arr: list[int]):
        self.n = len(arr)
        self.tree = [float('inf')] * (4 * self.n)
        if self.n > 0:
            self._build(arr, 1, 0, self.n - 1)
    
    def _build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
            return
        mid = (start + end) // 2
        self._build(arr, 2 * node, start, mid)
        self._build(arr, 2 * node + 1, mid + 1, end)
        self.tree[node] = min(self.tree[2 * node], self.tree[2 * node + 1])
    
    def query_min(self, l: int, r: int) -> int:
        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 float('inf')
        if l <= start and end <= r:
            return self.tree[node]
        mid = (start + end) // 2
        return min(
            self._query(2 * node, start, mid, l, r),
            self._query(2 * node + 1, mid + 1, end, l, r),
        )
    
    def update(self, idx: int, val: int) -> None:
        self._update(1, 0, self.n - 1, idx, val)
    
    def _update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
            return
        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] = min(self.tree[2 * node], self.tree[2 * node + 1])

Java implementation

class SegmentTree {
    private int[] tree;
    private int n;
    
    public SegmentTree(int[] arr) {
        n = arr.length;
        tree = new int[4 * n];
        build(arr, 1, 0, n - 1);
    }
    
    private void build(int[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        build(arr, 2 * node, start, mid);
        build(arr, 2 * node + 1, mid + 1, end);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    
    public int query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
    
    private int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;
        if (l <= start && end <= r) return tree[node];
        int mid = (start + end) / 2;
        return query(2 * node, start, mid, l, r) +
               query(2 * node + 1, mid + 1, end, l, r);
    }
    
    public void update(int idx, int val) {
        update(1, 0, n - 1, idx, val);
    }
    
    private void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
            return;
        }
        int mid = (start + end) / 2;
        if (idx <= mid) update(2 * node, start, mid, idx, val);
        else update(2 * node + 1, mid + 1, end, idx, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
}

Complexity summary

OperationTimeSpace
BuildO(n)O(n)
Point queryO(log n)-
Range queryO(log n)-
Point updateO(log n)-
Range update (lazy)O(log n)O(n) extra for lazy

When to use segment trees

Segment trees are the right tool when you need both range queries and updates on an array. If you only have queries and no updates, prefix sums or sparse tables may be simpler. If you only need point queries, a Fenwick tree (BIT) is easier to implement and has lower constant factors. Segment trees shine when you need flexibility: any associative operation (sum, min, max, GCD, XOR) can be plugged into the same framework.

Related articles