Introduction
A segment tree is a binary tree built over an array that lets you answer range queries — such as the sum, minimum, or maximum over any subrange — and perform point updates, all in O(log n) time. This is a major improvement over a plain array, where a range query takes O(n) and an update takes O(1), or a running prefix-sum array, where updates cost O(n). Segment trees are heavily used in competitive programming and in systems that need frequent range aggregation over mutable data, such as interval statistics, range minimum queries (RMQ), and computational geometry sweeps.
Cricket analogy: A segment tree over a season's ball-by-ball scores lets you instantly get the total runs or the highest score in any range of overs and update one ball's outcome in O(log n), unlike a plain scoreboard array needing O(n) to sum a range or a running-total sheet needing O(n) to fix one entry.
Structure/Syntax
class SegmentTree:
def __init__(self, data):
self.n = len(data)
self.tree = [0] * (4 * self.n) # size 4n is a safe upper bound
if self.n > 0:
self._build(data, 0, 0, self.n - 1)
def _build(self, data, node, start, end):
if start == end:
self.tree[node] = data[start]
return
mid = (start + end) // 2
left, right = 2 * node + 1, 2 * node + 2
self._build(data, left, start, mid)
self._build(data, right, mid + 1, end)
self.tree[node] = self.tree[left] + self.tree[right]Explanation
Each node of the segment tree represents an aggregate value (here, a sum) over a contiguous range [start, end] of the original array. The root covers the whole array; each internal node splits its range in half between its two children, and leaves correspond to single array elements. Because the tree has height O(log n), any range query can be answered by combining at most O(log n) nodes that exactly tile the query range, and a point update only needs to touch the O(log n) ancestors of the modified leaf, recomputing their aggregates on the way back up.
Cricket analogy: The segment tree's root sums an entire innings, its left and right children split it into first-half and second-half overs, and leaves are individual balls, so any range of overs can be summed by combining just O(log n) pre-built nodes instead of adding every ball.
Example
class SegmentTree:
def __init__(self, data):
self.n = len(data)
self.tree = [0] * (4 * self.n)
if self.n > 0:
self._build(data, 0, 0, self.n - 1)
def _build(self, data, node, start, end):
if start == end:
self.tree[node] = data[start]
return
mid = (start + end) // 2
left, right = 2 * node + 1, 2 * node + 2
self._build(data, left, start, mid)
self._build(data, right, mid + 1, end)
self.tree[node] = self.tree[left] + self.tree[right]
def update(self, idx, value, node=0, start=0, end=None):
if end is None:
end = self.n - 1
if start == end:
self.tree[node] = value
return
mid = (start + end) // 2
left, right = 2 * node + 1, 2 * node + 2
if idx <= mid:
self.update(idx, value, left, start, mid)
else:
self.update(idx, value, right, mid + 1, end)
self.tree[node] = self.tree[left] + self.tree[right]
def query(self, l, r, node=0, start=0, end=None):
if end is None:
end = self.n - 1
if r < start or end < l:
return 0 # no overlap
if l <= start and end <= r:
return self.tree[node] # total overlap
mid = (start + end) // 2
left, right = 2 * node + 1, 2 * node + 2
return (self.query(l, r, left, start, mid) +
self.query(l, r, right, mid + 1, end))
arr = [2, 4, 5, 7, 8, 9]
st = SegmentTree(arr)
print(st.query(1, 3)) # sum of arr[1..3] = 4+5+7 = 16
st.update(2, 10) # arr becomes [2, 4, 10, 7, 8, 9]
print(st.query(1, 3)) # 4+10+7 = 21Complexity
Building the tree costs O(n) since every array element and internal node is processed once. Both point update and range query run in O(log n), because each recursive call halves the range and only O(log n) nodes exactly tile any query interval. Space usage is O(n), typically implemented with an array of size 4n to safely hold a complete binary tree over n leaves. Range updates (adding a value to every element in a range) can also be supported in O(log n) using lazy propagation, which defers pushing updates to children until they are actually needed.
Cricket analogy: Building a segment tree over an entire season's ball-by-ball data costs O(n) since every ball and summary node is touched once, updating one ball's outcome or querying any range of overs costs O(log n), the tree needs about 4x the array size in scoreboard slots, and range updates like adding bonus runs to a whole over use lazy propagation to defer the work.
Key Takeaways
- A segment tree is a binary tree where each node aggregates a value (sum, min, max) over a contiguous array range.
- Range queries and point updates both run in O(log n), versus O(n) for naive array scans on every query.
- Building the tree takes O(n) time and O(n) extra space (commonly sized 4n for a recursive array-based implementation).
- Queries combine O(log n) nodes whose ranges exactly tile the requested interval, using partial/total/no-overlap cases.
- Lazy propagation extends segment trees to support O(log n) range updates, not just point updates.
Practice what you learned
1. What is the time complexity of a range sum query on a segment tree of n elements?
2. In the query() method, what does the case 'r < start or end < l' represent?
3. Why is the segment tree array typically allocated with size 4n rather than exactly 2n?
4. What technique allows a segment tree to perform range updates (updating every element in a range) in O(log n) instead of O(n)?
5. Compared to a plain prefix-sum array, what advantage does a segment tree offer?
Was this page helpful?
You May Also Like
Fenwick Trees (Binary Indexed Trees)
A compact array-based structure using the lowbit trick to compute prefix sums and point updates in O(log n).
Binary Trees
A hierarchical data structure where each node has at most two children, forming the foundation for many advanced tree structures.
Arrays in Data Structures
How arrays store elements in contiguous memory and why that layout drives their performance characteristics.