When Do You Need These?
Segment trees and Fenwick trees (Binary Indexed Trees / BIT) solve range query problems efficiently. When you need to: compute a range sum/min/max/GCD, update individual elements, and both operations must be fast — these data structures achieve O(log n) per operation. Naive arrays give O(1) update but O(n) range query; prefix sums give O(1) range query but O(n) update. Segment trees and BITs give O(log n) for both.
Fenwick Tree (Binary Indexed Tree)
The Fenwick tree (BIT) is the simpler of the two. It supports point update and prefix sum query efficiently using the binary representation of indices. Each index i stores the sum of a range determined by the lowest set bit of i.
class FenwickTree:
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1) # 1-indexed
def update(self, i, delta):
while i 0:
total += self.tree[i]
i -= i & (-i) # move to parent
return total
def range_query(self, l, r):
return self.query(r) - self.query(l - 1)
The key: i & (-i) isolates the lowest set bit. Update: add delta to index i, then move up the tree (i += i & (-i)). Query: sum from i down to 1 (i -= i & (-i)). Both operations touch at most O(log n) nodes. Space O(n).
Segment Tree
The segment tree is more flexible — it can handle any associative operation (sum, min, max, GCD, product) and range updates (not just point updates). Built as a binary tree where each node stores the aggregate for its range. The root covers [0, n-1]; leaves cover single elements.
class SegmentTree:
def __init__(self, nums):
self.n = len(nums)
self.tree = [0] * (4 * self.n)
self._build(nums, 0, 0, self.n - 1)
def _build(self, nums, node, start, end):
if start == end:
self.tree[node] = nums[start]
else:
mid = (start + end) // 2
self._build(nums, 2*node+1, start, mid)
self._build(nums, 2*node+2, mid+1, end)
self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]
def update(self, node, start, end, idx, val):
if start == end:
self.tree[node] = val
else:
mid = (start + end) // 2
if idx <= mid:
self.update(2*node+1, start, mid, idx, val)
else:
self.update(2*node+2, mid+1, end, idx, val)
self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]
def query(self, node, start, end, l, r):
if r < start or end < l:
return 0 # out of range identity
if l <= start and end <= r:
return self.tree[node] # completely within range
mid = (start + end) // 2
return (self.query(2*node+1, start, mid, l, r) +
self.query(2*node+2, mid+1, end, l, r))
Build: O(n). Update and query: O(log n). Space: O(4n) for the tree array.
Range Update with Lazy Propagation
Standard segment tree updates one element at a time. For range updates (“add 5 to all elements in [l, r]”), naive application is O(n log n). Lazy propagation defers updates: when updating a range, mark the node with a “lazy” tag instead of updating all children immediately. Children are updated only when they are next accessed (either for a query or further update). This reduces range updates from O(n log n) to O(log n).
Classic Interview Problems
Range Sum Query – Mutable (LC 307): given an array, support pointUpdate(i, val) and rangeSum(l, r). Use Fenwick tree or segment tree. O(log n) per operation.
Count of Smaller Numbers After Self (LC 315): for each element, count elements to its right that are smaller. Process from right to left: for each element nums[i], query BIT for prefix sum [0, nums[i]-1] (count of numbers already inserted that are smaller). Then insert nums[i] into BIT. Requires coordinate compression (map values to indices 1..n). O(n log n).
Range Minimum Query: build a segment tree that stores the minimum in each range instead of the sum. Query returns the minimum in [l, r]. Used in LCA algorithms and string suffix array construction.
My Calendar III (LC 732): given events with start/end times, find the maximum number of concurrent events after each insertion. Difference array + BIT: for event [start, end], update BIT[start] += 1 and BIT[end] -= 1. Maximum prefix sum = maximum concurrent bookings. Alternatively, segment tree with lazy propagation on time coordinates.
Coordinate Compression: when values are large (up to 10^9) but there are few unique values (≤ 10^5), compress: sort unique values, map each to its rank. Replace values with ranks before using BIT/segment tree.
Choosing Between Fenwick and Segment Tree
Use Fenwick (BIT) when: only point updates + prefix/range sum queries; simpler code (20 lines vs 50); O(n) space vs O(4n). Use Segment Tree when: range updates (lazy propagation), operations other than sum (min, max, GCD), or interval overlap counting (needs range update + range query). In interviews, Fenwick tree is often sufficient and easier to implement correctly under time pressure.