Introduction to Segment Trees
A Segment Tree is a powerful data structure used for answering range queries and performing point or range updates on an array in logarithmic time. It is built on the principle of divide-and-conquer: the array is recursively split into segments, and each node of the tree stores precomputed information about a specific interval of the array.
Unlike a naive approach that scans the entire range for each query — costing O(n) time per operation — a Segment Tree reduces both query and update operations to O(log n). This makes it indispensable in competitive programming, database indexing, and any scenario requiring repeated range computations over mutable data.
Why Segment Trees Matter
Consider an array of one million integers where you need to repeatedly answer questions like "What is the sum of elements from index 200 to 500?" or "What is the minimum value between index 10 and 1000?" — and the array is constantly being updated. A linear scan for each query would be prohibitively slow.
Segment Trees solve this by precomputing partial results in a tree structure. Each node represents a segment of the array and stores an aggregate value (sum, min, max, GCD, etc.) for that segment. When a query arrives, the tree combines relevant nodes to produce the answer without visiting every element.
Key Operations and Their Complexity
- Build: O(n) — Constructed once from the initial array.
- Point Update: O(log n) — Update a single element and propagate the change upward.
- Range Query: O(log n) — Query an interval by combining at most 4*log(n) nodes.
- Space: O(4n) — The tree is stored in an array of size at most 4n to safely accommodate all nodes.
How a Segment Tree Works
The tree is typically represented as an array where the root is at index 1. For any node at index i, its left child is at 2*i and its right child is at 2*i + 1. Each node covers a range [l, r], and if l == r, it is a leaf node corresponding to a single array element.
For internal nodes, the stored value is computed by combining the values of its two children. For a sum Segment Tree, the parent stores the sum of its children. For a min Segment Tree, it stores the minimum of its children.
Implementation: Range Sum Segment Tree
Below is a complete implementation of a Segment Tree supporting point updates and range sum queries. The code is written in C++ for clarity and performance.
#include <iostream>
#include <vector>
using namespace std;
class SegmentTree {
private:
vector<int> tree;
int n;
// Build the tree recursively
void build(const vector<int>& arr, int node, int start, int end) {
if (start == end) {
// Leaf node stores the array element
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
int leftChild = 2 * node;
int rightChild = 2 * node + 1;
build(arr, leftChild, start, mid);
build(arr, rightChild, mid + 1, end);
// Internal node stores the sum of children
tree[node] = tree[leftChild] + tree[rightChild];
}
}
// Point update: set arr[idx] = val
void update(int node, int start, int end, int idx, int val) {
if (start == end) {
tree[node] = val;
} else {
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];
}
}
// Range query: sum of elements in [l, r]
int query(int node, int start, int end, int l, int r) {
if (r < start || l > end) {
// No overlap
return 0;
}
if (l <= start && end <= r) {
// Complete overlap
return tree[node];
}
// Partial overlap: query both children
int mid = (start + end) / 2;
int leftSum = query(2 * node, start, mid, l, r);
int rightSum = query(2 * node + 1, mid + 1, end, l, r);
return leftSum + rightSum;
}
public:
SegmentTree(const vector<int>& arr) {
n = arr.size();
tree.resize(4 * n);
build(arr, 1, 0, n - 1);
}
void update(int idx, int val) {
update(1, 0, n - 1, idx, val);
}
int query(int l, int r) {
return query(1, 0, n - 1, l, r);
}
};
int main() {
vector<int> arr = {1, 3, 5, 7, 9, 11};
SegmentTree st(arr);
cout << "Sum of [1, 3]: " << st.query(1, 3) << endl; // 3 + 5 + 7 = 15
cout << "Sum of [0, 5]: " << st.query(0, 5) << endl; // 36
st.update(1, 10); // arr[1] = 10
cout << "Sum of [1, 3] after update: " << st.query(1, 3) << endl; // 10 + 5 + 7 = 22
return 0;
}
Understanding the Query Logic
The query function handles three cases at each node. If the query range does not overlap with the node's range, it returns the identity element (0 for sum). If the node's range is fully contained within the query range, it returns the precomputed value. Otherwise, it recurses into both children and combines their results. This ensures that only O(log n) nodes are visited per query.
Implementation: Range Minimum Segment Tree
Changing the aggregate operation is straightforward. For a minimum query tree, replace addition with min() and use a large sentinel value (like INT_MAX) as the identity element for the no-overlap case.
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
class MinSegmentTree {
private:
vector<int> tree;
int n;
void build(const vector<int>& arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
build(arr, 2 * node, start, mid);
build(arr, 2 * node + 1, mid + 1, end);
tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}
}
int query(int node, int start, int end, int l, int r) {
if (r < start || l > end) {
return INT_MAX; // Identity for min operation
}
if (l <= start && end <= r) {
return tree[node];
}
int mid = (start + end) / 2;
return min(
query(2 * node, start, mid, l, r),
query(2 * node + 1, mid + 1, end, l, r)
);
}
public:
MinSegmentTree(const vector<int>& arr) {
n = arr.size();
tree.resize(4 * n);
build(arr, 1, 0, n - 1);
}
int query(int l, int r) {
return query(1, 0, n - 1, l, r);
}
};
int main() {
vector<int> arr = {5, 2, 6, 1, 9, 3};
MinSegmentTree mst(arr);
cout << "Min of [0, 5]: " << mst.query(0, 5) << endl; // 1
cout << "Min of [2, 4]: " << mst.query(2, 4) << endl; // 1
return 0;
}
Lazy Propagation for Range Updates
When you need to update an entire range (for example, add a value to all elements from index 2 to 5), a naive point-by-point update would cost O(n log n). Lazy Propagation defers updates to child nodes until they are actually needed, bringing range updates down to O(log n).
The idea is to maintain a separate lazy array. When a range update is applied to a node, the update is recorded in lazy but not immediately pushed to its children. When a query or update later descends into those children, the pending lazy value is propagated downward.
#include <iostream>
#include <vector>
using namespace std;
class LazySegmentTree {
private:
vector<long long> tree;
vector<long long> lazy;
int n;
void build(const vector<int>& arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
} else {
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];
}
}
void pushDown(int node, int start, int end) {
if (lazy[node] != 0) {
int mid = (start + end) / 2;
// Apply lazy value to left child
tree[2 * node] += lazy[node] * (mid - start + 1);
lazy[2 * node] += lazy[node];
// Apply lazy value to right child
tree[2 * node + 1] += lazy[node] * (end - mid);
lazy[2 * node + 1] += lazy[node];
// Clear lazy value at current node
lazy[node] = 0;
}
}
void rangeUpdate(int node, int start, int end, int l, int r, int val) {
if (r < start || l > end) return;
if (l <= start && end <= r) {
tree[node] += (long long)val * (end - start + 1);
lazy[node] += val;
return;
}
pushDown(node, start, end);
int mid = (start + end) / 2;
rangeUpdate(2 * node, start, mid, l, r, val);
rangeUpdate(2 * node + 1, mid + 1, end, l, r, val);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
long long rangeQuery(int node, int start, int end, int l, int r) {
if (r < start || l > end) return 0;
if (l <= start && end <= r) return tree[node];
pushDown(node, start, end);
int mid = (start + end) / 2;
return rangeQuery(2 * node, start, mid, l, r)
+ rangeQuery(2 * node + 1, mid + 1, end, l, r);
}
public:
LazySegmentTree(const vector<int>& arr) {
n = arr.size();
tree.resize(4 * n, 0);
lazy.resize(4 * n, 0);
build(arr, 1, 0, n - 1);
}
void rangeUpdate(int l, int r, int val) {
rangeUpdate(1, 0, n - 1, l, r, val);
}
long long rangeQuery(int l, int r) {
return rangeQuery(1, 0, n - 1, l, r);
}
};
int main() {
vector<int> arr = {1, 3, 5, 7, 9, 11};
LazySegmentTree lst(arr);
cout << "Sum of [1, 3]: " << lst.rangeQuery(1, 3) << endl; // 15
lst.rangeUpdate(1, 3, 10); // Add 10 to indices 1, 2, 3
cout << "Sum of [1, 3] after range update: " << lst.rangeQuery(1, 3) << endl; // 45
cout << "Sum of [0, 5]: " << lst.rangeQuery(0, 5) << endl; // 66
return 0;
}
Time Complexity Analysis
Build Complexity
The build function visits every node exactly once. Since a Segment Tree has at most 2n - 1 nodes (for n leaves and n - 1 internal nodes), the build operation runs in O(n) time.
Query Complexity
At each level of the tree, the query visits at most 4 nodes: 2 on the left boundary and 2 on the right boundary of the query range, plus possibly some fully covered nodes in between. Since the tree has O(log n) levels, the total number of visited nodes is O(log n). This gives range queries a time complexity of O(log n).
Update Complexity
A point update modifies a single leaf and propagates the change up to the root. The path from any leaf to the root has length O(log n), so point updates run in O(log n). Range updates with lazy propagation also run in O(log n) because the lazy mechanism ensures that at most O(log n) nodes are directly modified per update.
Space Complexity
The tree array requires O(4n) space in the worst case. This is because the next power of two above n may double the number of leaves, and the array-based representation allocates space for all possible nodes. The lazy array adds another O(4n), bringing the total to O(n) overall.
Best Practices
- Always allocate 4n space: Allocating exactly 2n can cause out-of-bounds errors for certain array sizes. Using 4n is a safe convention adopted across the competitive programming community.
- Use 1-based indexing for the tree: Starting the root at index 1 simplifies the child-parent relationship: left child is
2*i, right child is2*i + 1, and parent isi/2. - Choose the correct identity element: For sum, the identity is 0. For min, it is
INT_MAX. For max, it isINT_MIN. For GCD, it is 0. Using the wrong identity produces incorrect results in no-overlap cases. - Prefer iterative implementations for speed: Recursive Segment Trees are easier to understand, but iterative versions (using bottom-up loops) are faster in practice due to reduced function call overhead.
- Consider alternative data structures: If updates are rare and queries are frequent, a Prefix Sum array may suffice. If you need dynamic range queries with complex operations, a Fenwick Tree (Binary Indexed Tree) is often simpler and faster for invertible operations like sum.
- Watch for integer overflow: When storing sums, use
long longto avoid overflow, especially when combining large ranges or applying range additions.
Iterative Segment Tree
For performance-critical applications, an iterative bottom-up Segment Tree eliminates recursion overhead. This version is particularly elegant for commutative operations like sum and min.
#include <iostream>
#include <vector>
using namespace std;
class IterativeSegmentTree {
private:
int n;
vector<long long> tree;
public:
IterativeSegmentTree(const vector<int>& arr) {
n = arr.size();
tree.resize(2 * n);
// Place leaves at indices n to 2n-1
for (int i = 0; i < n; i++) {
tree[n + i] = arr[i];
}
// Build internal nodes bottom-up
for (int i = n - 1; i > 0; i--) {
tree[i] = tree[2 * i] + tree[2 * i + 1];
}
}
void update(int idx, int val) {
idx += n;
tree[idx] = val;
for (int i = idx / 2; i > 0; i /= 2) {
tree[i] = tree[2 * i] + tree[2 * i + 1];
}
}
long long query(int l, int r) {
// Query sum on [l, r) — note r is exclusive
long long result = 0;
l += n;
r += n;
while (l < r) {
if (l % 2 == 1) result += tree[l++];
if (r % 2 == 1) result += tree[--r];
l /= 2;
r /= 2;
}
return result;
}
};
int main() {
vector<int> arr = {1, 3, 5, 7, 9, 11};
IterativeSegmentTree ist(arr);
cout << "Sum of [1, 4): " << ist.query(1, 4) << endl; // 3 + 5 + 7 = 15
ist.update(1, 10);
cout << "Sum of [1, 4) after update: " << ist.query(1, 4) << endl; // 22
return 0;
}
Note that the iterative version uses half-open intervals [l, r) for queries, which is a common convention that simplifies the loop logic. The space complexity is exactly 2n, making it more memory-efficient than the recursive version.
Conclusion
Segment Trees are a versatile and efficient data structure for handling range queries and updates on arrays. By organizing precomputed results in a binary tree, they achieve O(log n) time for both queries and updates while using only O(n) space. Whether you need simple sum queries, range minimum queries, or complex range updates with lazy propagation, the Segment Tree provides a robust foundation. Understanding the recursive structure, mastering lazy propagation, and knowing when to choose the iterative variant will equip you to tackle a wide range of algorithmic problems with confidence and efficiency.