Segment Tree & Fenwick Tree

DSA · Advanced

Definition

Segment and Fenwick trees answer range queries and point updates in O(log n).

Needed when an array changes between range-sum queries.

Diagram

Flowchart

Example: Fenwick prefix sums

n = 5; bit = [0] * (n + 1)
def add(i, v):
    while i <= n: bit[i] += v; i += i & -i
def pre(i):
    s = 0
    while i: s += bit[i]; i -= i & -i
    return s
for i, v in enumerate([3, 2, 5, 1, 4], 1): add(i, v)
print(pre(3), pre(5) - pre(2))

Output: 10 10

Complexity

Build O(n log n) · Query/Update O(log n)

Key points

Fenwick is shorter; segment tree is more flexible
Lazy propagation handles range updates

Interview questions

Prefix sum vs Fenwick?

Prefix sums need O(n) per update; Fenwick needs O(log n).