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.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the difference between a Fenwick tree (BIT) and a segment tree?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Both support O(log n) point update and range query, but they differ in flexibility and complexity. Fenwick tree (BIT): simpler implementation (~10 lines), O(n) space, supports only prefix sum (and by extension range sum). The key insight is the lowbit trick: i & (-i) isolates the lowest set bit, determining which range each index is responsible for. Limited to commutative, invertible operations (sum, XOR, product over a field). Cannot handle range updates or arbitrary non-invertible operations (min/max). Segment tree: more complex (~40 lines), O(4n) space, supports any associative operation (sum, min, max, GCD, product). Supports range updates via lazy propagation. More flexible and generalizable. Can be extended to 2D (segment tree of segment trees) for 2D range queries. Rule of thumb: use Fenwick tree when you only need range sum with point updates u2014 it’s faster to implement correctly under interview pressure. Use segment tree when you need range min/max, range updates (add X to all elements in [l, r]), or the operation is not invertible (can’t subtract to get range query from prefix queries).”
}
},
{
“@type”: “Question”,
“name”: “How do you solve “Count of Smaller Numbers After Self” using a Fenwick tree?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Count of Smaller Numbers After Self (LC 315) asks: for each element, how many elements to its right are smaller? Fenwick tree approach: process elements from right to left. For each element nums[i]: (1) Query BIT for prefix sum [1, nums[i]-1] u2014 this gives the count of already-processed (to the right of i) elements with value < nums[i]. Store this as result[i]. (2) Update BIT at position nums[i] with +1 u2014 record that this value has been seen. Coordinate compression is required since values can be large (up to 10^4 or 10^9): map all unique values to ranks 1..n. Example: nums = [5, 2, 6, 1]. Compress to ranks [3, 2, 4, 1]. Process right to left: i=3 (val=1, rank=1): query BIT[0..0] = 0, update BIT[1]; result[3]=0. i=2 (val=6, rank=4): query BIT[0..3] = 1, update BIT[4]; result[2]=1. i=1 (val=2, rank=2): query BIT[0..1] = 1, update BIT[2]; result[1]=1. i=0 (val=5, rank=3): query BIT[0..2] = 2, update BIT[3]; result[0]=2. Final: [2,1,1,0]. O(n log n) time with coordinate compression."
}
},
{
"@type": "Question",
"name": "What is lazy propagation in a segment tree and when do you need it?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Lazy propagation is an optimization for segment trees that defers range updates until necessary. Without it, "add 5 to all elements in [l, r]" requires updating O(r-l+1) leaf nodes u2014 O(n) per update. With lazy propagation: mark intermediate nodes with a lazy tag (the pending update) instead of propagating to children immediately. When a query or update later accesses a node's children, first push the lazy tag down (apply to children and clear the parent's tag) before processing. This amortizes the cost u2014 each element is updated at most O(log n) times regardless of how many range updates overlap. Implementation: add a lazy array to the segment tree. In update(): if the current node's range is fully within [l, r], apply the update to this node and set lazy[node] = update_value. In query() and further update(), before accessing children: if lazy[node] != 0, push down (apply lazy to both children, clear lazy[node]). Time complexity remains O(log n) per operation. Required for: "add X to range [l, r]", "set all elements in [l, r] to X", "reverse all bits in [l, r]", and other range modification + range query combinations."
}
}
]
}