Intermediate LevelData Structures & Algorithms
What is a Segment Tree and when is it better than a Prefix Sum?
ā Interview Prompt: Explain Segment Trees, O(N) build, O(log N) range queries and point updates, and when they outperform prefix sum arrays.
A Segment Tree is a binary tree where each node stores aggregate information (sum, min, max) of a range of the original array.
Complexity:
| Operation | Prefix Sum | Segment Tree |
|---|---|---|
| Build | $O(N)$ | $O(N)$ |
| Range Query | $O(1)$ | $O(\log N)$ |
| Point Update | $O(N)$ rebuild | $O(\log N)$ |
When to Use Segment Tree:
ā¢
Dynamic arrays with frequent updates + queries ā prefix sum requires $O(N)$ rebuild on update.
ā¢
Range min/max queries (prefix sum only handles sums).
ā¢
Lazy propagation for range updates in $O(\log N)$.
Code Implementation Example
typescript
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 = (lo + hi) >> 1;
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 = (lo + hi) >> 1;
return this.query(l, r, 2 * node + 1, lo, mid)
+ this.query(l, r, 2 * node + 2, mid + 1, hi);
}
}š”Segment Tree with O(N) build and O(log N) range sum queries.
šÆ Interview Key Takeaway
Use Segment Trees when both range queries AND point updates are frequent. Prefix sums give O(1) query but O(N) update.
#DSA#Segment Tree#Range Queries#Data Structures#Intermediate
Back to all Data Structures & Algorithms Questionsā