Segment Trees

Also Known As

TL;DR

Explanation

Each node stores an aggregate (sum, min, max) over a range. Leaves represent individual elements. Build: O(n). Range query and point update: O(log n) each. Lazy propagation extends to range updates in O(log n). Compare to prefix sum: prefix sum allows O(1) range queries but O(n) updates; segment tree provides O(log n) for both — choose based on query/update ratio.

Common Misconception

Why It Matters

Common Mistakes

• Not implementing lazy propagation for range updates — naive update is O(n)
• Off-by-one errors in range boundaries
• Using segment tree for static data — prefix sum is simpler
• Not handling out-of-range queries gracefully

Code Examples

// O(n) range sum — slow for large arrays:
function rangeSum(array $arr, int $l, int $r): int {
    return array_sum(array_slice($arr, $l, $r - $l + 1));
}
// 1000 queries on 1M element array: 1 billion operations

// Segment tree — O(log n) per query and update:
class SegmentTree {
    private array $tree;
    public function query(int $l, int $r): int { /* O(log n) */ }
    public function update(int $pos, int $val): void { /* O(log n) */ }
}

References

• ↗ https://en.wikipedia.org/wiki/Segment_tree

Tags

Related Terms