Segment Tree from Scratch (2026)
A Segment Tree is a versatile binary tree data structure used for answering range queries and updating array elements in logarithmic time. It stores aggregate information (sum, min, max, gcd, etc.) for segments of an array. Each leaf represents a single element, and each internal node represents the combined value of its segment.
Segment Trees support point updates and range queries in O(log n) time. With lazy propagation, they can handle range updates (e.g., adding a value to all elements in a range) also in O(log n). They are widely used in competitive programming and computational geometry problems.
Building and Querying
Build the tree recursively from the array — leaf nodes store individual elements, internal nodes store the aggregate of children (e.g., sum). A range query traverses the tree, combining results from fully covered segments. Both operations run in O(log n).
void build(int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
}
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);
}Lazy Propagation
Lazy propagation defers updates to child nodes. When a range update is applied, we mark the current node as 'lazy' instead of updating all descendants immediately. The pending update is pushed down only when a query or update actually needs the children's values.
void updateRange(int node, int start, int end, int l, int r, int val) {
if (lazy[node] != 0) {
tree[node] += (end - start + 1) * lazy[node];
if (start != end) {
lazy[2 * node] += lazy[node];
lazy[2 * node + 1] += lazy[node];
}
lazy[node] = 0;
}
if (r < start || end < l) return;
if (l <= start && end <= r) {
tree[node] += (end - start + 1) * val;
if (start != end) {
lazy[2 * node] += val;
lazy[2 * node + 1] += val;
}
return;
}
int mid = (start + end) / 2;
updateRange(2 * node, start, mid, l, r, val);
updateRange(2 * node + 1, mid + 1, end, l, r, val);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}Frequently Asked Questions
What is the difference between Segment Tree and Fenwick Tree?
Fenwick trees are simpler and more memory-efficient but only support prefix queries and point updates. Segment trees are more general, supporting range updates (with lazy propagation) and arbitrary associative operations.
How much memory does a Segment Tree need?
A typical implementation uses an array of size 4×n, which is sufficient for any n. This is because the tree is stored as a nearly complete binary tree.
Originally published on Ayodhyyya. Last updated June 1, 2026.