Segment Trees
debt(d7/e5/b3/t5)
Closest to 'only careful code review or runtime testing' (d7), since detection_hints.automated is no — recognizing that O(n) range queries should be a segment tree requires human review or performance profiling under load.
Closest to 'touches multiple files / significant refactor in one component' (e5), since introducing a segment tree replaces naive array logic with a new data structure plus lazy propagation, affecting query/update paths in one component.
Closest to 'localised tax' (b3), since the segment tree is typically encapsulated in one module handling range queries; rest of codebase is unaffected.
Closest to 'notable trap' (t5), grounded in the misconception that prefix sums are equivalent — plus off-by-one boundary errors and missing lazy propagation are documented gotchas most devs eventually learn.
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) */ }
}