Segment Trees & Fenwick Trees
Week 9
Segment Tree
Supports range queries and point updates in O(log n).
Array: [2, 4, 6, 8, 10]
Segment tree (range sum):
30
/ \
12 18
/ \ / \
2 10 14 4
/ \ / \
4 6 8 6| Operation | Complexity |
|---|---|
| Build | O(n) |
| Range query | O(log n) |
| Point update | O(log n) |
| Range update + lazy | O(log n) |
Fenwick Tree (Binary Indexed Tree)
Simpler implementation, supports prefix sum queries and point updates.
class BIT {
constructor(n) { this.tree = Array(n + 1).fill(0); }