Pattern Reference
Segment Tree Basics
"Point updates, range queries, building and querying segment trees."
Loading...
Deep Dive Tutorial
Segment tree stores aggregates at nodes. Node i covers a range; left child = node 2i, right child = node 2i+1 (1-indexed). Build by splitting range and combining children. Range query: recursively combine left/right where range overlaps. Point update: update the leaf, then propagate up. 1-indexed array of size 4n is sufficient for n elements.
Segment tree: sum with point update and range query
class SegmentTree {
constructor(n) {
this.n = n;
this.tree = new Array(4 * n).fill(0);
}
build(arr, node = 1, start = 0, end = this.n - 1) {
if (start === end) { this.tree[node] = arr[start]; return; }
const mid = (start + end) >> 1;
this.build(arr, 2*node, start, mid);
this.build(arr, 2*node+1, mid+1, end);
this.tree[node] = this.tree[2*node] + this.tree[2*node+1];
}
update(idx, val, node = 1, start = 0, end = this.n - 1) {
if (start === end) { this.tree[node] = val; return; }
const mid = (start + end) >> 1;
if (idx <= mid) this.update(idx, val, 2*node, start, mid);
else this.update(idx, val, 2*node+1, mid+1, end);
this.tree[node] = this.tree[2*node] + this.tree[2*node+1];
}
query(l, r, node = 1, start = 0, end = this.n - 1) {
if (r < start || end < l) return 0; // identity for sum
if (l <= start && end <= r) return this.tree[node];
const mid = (start + end) >> 1;
return this.query(l, r, 2*node, start, mid) +
this.query(l, r, 2*node+1, mid+1, end);
}
}Worked Problems
tree-pine
Segment tree vs Fenwick tree:
- Fenwick: simpler code, prefix sum only (can do point update + range sum)
- Segment tree: range min/max, any associative operation, can add lazy propagation
- Use Fenwick for competitive sum problems, segment tree for min/max or range update
4n array size: Works for n up to the array bound. Alternatively, use bottom-up iterative segment tree (2n size) for simpler code.
Merge function: Sum, min, max, GCD, XOR — any associative operation with an identity element works. Just swap out the merge and identity (0 for sum, ∞ for min, -∞ for max).
- Fenwick: simpler code, prefix sum only (can do point update + range sum)
- Segment tree: range min/max, any associative operation, can add lazy propagation
- Use Fenwick for competitive sum problems, segment tree for min/max or range update
4n array size: Works for n up to the array bound. Alternatively, use bottom-up iterative segment tree (2n size) for simpler code.
Merge function: Sum, min, max, GCD, XOR — any associative operation with an identity element works. Just swap out the merge and identity (0 for sum, ∞ for min, -∞ for max).