Segment Tree
Tree for fast range queries (sum, min, max) with O(log n) update.
How it works
A Segment Tree is a binary tree where each node stores aggregate information (e.g. sum, min, max) over a contiguous sub-array (segment). The root covers the full array `[0, n-1]`. Each internal node `i` covers a range `[lo, hi]` and its children cover `[lo, mid]` and `[mid+1, hi]` where `mid = ⌊(lo+hi)/2⌋`.
Build: O(n) — fill each leaf with the corresponding array element, then each internal node gets the combined value of its children.
Query: O(log n) — at each node, if the query range fully contains the node's range, return its stored value; if no overlap, return the identity (0 for sum); otherwise recurse into both children.
Update: O(log n) — walk from root to the target leaf, updating each node on the path.
Complexity
Visualizer
Where it's used in the real world
Apache Spark / distributed query engines
Range aggregate queries on partitioned dataSegment-tree-like partition trees are used internally when planning range-aggregate queries over time-series or sorted numeric columns, collapsing partition statistics in O(log n) steps.
Competitive programming
Range min/max/sum with lazy propagationSegment trees (often with lazy propagation) handle interval update + range query problems — the workhorse for problems like 'range add, range sum' on Codeforces/LeetCode.
GIS / spatial databases
1-D interval stabbing / coverage queriesSegment trees underlie efficient 1-D interval stabbing queries; PostGIS and R-tree variants use the same divide-and-conquer principle for 2-D rectangles.
Text editors (rope data structure)
Character count / line count in rangesThe rope used in editors like VS Code aggregates character/line counts at each internal node — equivalent to a segment tree supporting O(log n) range count and O(log n) insert/delete.
Implementation
class SegmentTree {
private tree: number[];
private n: number;
constructor(arr: number[]) {
this.n = arr.length;
this.tree = new Array(4 * this.n).fill(0);
this.build(arr, 0, 0, this.n - 1);
}
private build(arr: number[], node: number, lo: number, hi: number): void {
if (lo === hi) {
this.tree[node] = arr[lo];
return;
}
const mid = Math.floor((lo + hi) / 2);
this.build(arr, 2 * node + 1, lo, mid);
this.build(arr, 2 * node + 2, mid + 1, hi);
this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
}
query(l: number, r: number, node = 0, lo = 0, hi = this.n - 1): number {
if (r < lo || hi < l) return 0;
if (l <= lo && hi <= r) return this.tree[node];
const mid = Math.floor((lo + hi) / 2);
return (
this.query(l, r, 2 * node + 1, lo, mid) +
this.query(l, r, 2 * node + 2, mid + 1, hi)
);
}
update(pos: number, val: number, node = 0, lo = 0, hi = this.n - 1): void {
if (lo === hi) { this.tree[node] = val; return; }
const mid = Math.floor((lo + hi) / 2);
if (pos <= mid) this.update(pos, val, 2 * node + 1, lo, mid);
else this.update(pos, val, 2 * node + 2, mid + 1, hi);
this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
}
}
const st = new SegmentTree([1, 3, 5, 7, 9, 11]);
console.log(st.query(1, 4)); // 24 (3+5+7+9)
st.update(2, 10);
console.log(st.query(1, 4)); // 29 (3+10+7+9)