Interview frequency: …
Short answer
Use them when you need arithmetic range queries over an array that changes over time (such as range sum or minimum) along with frequent dynamic item updates, all in O(log N).
Explanation
If the array is static, a Prefix Sum table can calculate the sum in O(1), but updating costs O(N). Directly updating array items costs O(1), but querying costs O(N). Segment and Fenwick trees balance both: updates and range queries each take O(log N). Fenwick trees are simpler and use less memory, while Segment Trees support more complex queries such as minimum and range updates (Lazy Propagation).
Code example
class Fenwick: # Binary Indexed Tree: point update + prefix sum in O(log n)
def __init__(self, n):
self.tree = [0] * (n + 1) # 1-based
def update(self, i, delta):
while i < len(self.tree):
self.tree[i] += delta
i += i & -i # jump to the next node that covers index i
def prefix_sum(self, i):
total = 0
while i > 0:
total += self.tree[i]
i -= i & -i # drop the lowest set bit
return total
f = Fenwick(8)
f.update(3, 5)
f.update(5, 2)
print(f.prefix_sum(5) - f.prefix_sum(2)) # sum of positions 3..5 → 7Common mistakes
- Implementing a full Segment Tree for a fixed array whose values never change, when a simple Prefix Sum array is enough for O(1) queries.