Fenwick Trees and Segment Trees: When Coding Interviews Need Fast Range Queries

Most coding interview questions can be solved with arrays, hash maps, heaps and graphs. But every so often, especially at companies with harder onsite loops, you get a problem that needs fast range queries with updates. That's where Fenwick trees (binary indexed trees) and segment trees come in. You don't need to be a competitive programmer to use them, but you should recognize when they're needed and be able to write one calmly. THE SIGNAL Watch for a problem that combines two operations on an array: - update a value (or a range of values), and - ask for a sum, minimum or maximum over a range, with many of both. A plain array gives O(1) updates but O(n) queries. A prefix-sum array gives O(1) queries but O(n) updates. When both happen often, you need O(log n) for each. Classic examples: "Range Sum Query - Mutable", "Count of Smaller Numbers After Self", counting inversions, and "My Calendar" style booking problems. FENWICK TREE (BINARY INDEXED TREE) A Fenwick tree stores partial sums so that both point updates and prefix-sum queries take O(log n). It's short enough to write from memory: class Fenwick: def __init__(self, n): self.n = n self.t = [0] * (n + 1) # 1-indexed def add(self, i, delta): while i <= self.n: self.t[i] += delta i += i & -i def prefix(self, i): s = 0 while i > 0: s += self.t[i] i -= i & -i return s def range_sum(self, l, r): return self.prefix(r) - self.prefix(l - 1) The key trick is i & -i, which isolates the lowest set bit. Each index is responsible for a block of the array whose length equals that lowest bit. When to choose it: sums (or other invertible operations like XOR) with point updates. It's the fastest thing to write under time pressure. SEGMENT TREE A segment tree is a binary tree where each node covers a range and stores an aggregate (sum, min, max, gcd). It handles operations that aren't invertible, like range minimum, which a Fenwick tree can't do directly. class SegTree: def __init__(self, nums): self.n = len(nums) self.t = [0] * (2 * self.n) self.t[self.n:] = nums for i in range(self.n - 1, 0, -1): self.t[i] = min(self.t[2*i], self.t[2*i+1]) def update(self, i, val): i += self.n self.t[i] = val while i > 1: i //= 2 self.t[i] = min(self.t[2*i], self.t[2*i+1]) def query(self, l, r): # inclusive l, exclusive r res = float('inf') l += self.n; r += self.n while l < r: if l & 1: res = min(res, self.t[l]); l += 1 if r & 1: r -= 1; res = min(res, self.t[r]) l //= 2; r //= 2 return res This iterative version is compact and avoids recursion bugs. Range updates need lazy propagation, which is rarely expected unless the interviewer hints at it. HOW TO HANDLE IT IN THE INTERVIEW 1. State the brute force and its complexity first. 2. Name the bottleneck: "updates and range queries are both frequent." 3. Propose the structure and say which one and why ("sum with point updates, so a Fenwick tree"). 4. Write it cleanly, then test with a tiny array of three or four elements. Common mistakes: mixing 0-indexed and 1-indexed positions, forgetting that coordinate compression is needed when values are large, and over-engineering with lazy propagation when it isn't required. PRACTICE TIP Implement each structure from scratch three times on different days until you can do it in under ten minutes. The bigger challenge in a live round is usually explaining your choice while you code. Some candidates use tools like Linkjob AI (https://linkjob.ai), which gives real-time help during live job interviews and technical interviews, to keep their explanation organized under pressure. Whatever your prep method, recognizing the "update plus range query" signal is what turns this from a hard problem into a familiar one.