Fenwick Tree (Binary Indexed Tree) Interview Questions
Last updated 2026-11-19
A Fenwick tree, or binary indexed tree, stores prefix sums in an array of the same size as the input and supports point update and prefix query in O(log n). It is shorter than a segment tree, uses less memory, and is the usual choice when you only need sums or counts.
The problems below begin with the structure itself and move through inversions, range updates, binary lifting and offline distinct-count queries. Each has Python and Java code with complexity and edge cases. When you need min, max or range updates with arbitrary operations, see segment tree interview questions. Counting problems like these also connect to sorting and merge-based thinking.
| Update and prefix query | O(log n) |
|---|---|
| Memory | n + 1 numbers |
| Indexing | 1-based, via i & -i |
| Limits | Needs an invertible operation such as sum |
The pattern and when to spot it
Use a Fenwick tree when the problem needs repeated prefix or range sums under updates, or counting how many earlier elements are smaller or larger than the current one. The counting use is the most common in interviews: compress the values to ranks, then use the BIT as a frequency table that answers how many values are at most r in O(log n).
Because the structure stores prefix sums, the operation must be invertible so that a range is the difference of two prefixes. Sum, count and xor fit; min and max do not for general ranges. Combining two BITs gives range update with range query, and a difference BIT gives range update with point query. If values are huge, compress them first, and when queries can be answered offline, sort them to unlock tricks like last-occurrence counting.
Common pitfalls
- Using index 0, which loops forever on update because i & -i is 0.
- Forgetting to compress values before using them as indexes.
- Updating with the new value instead of the difference from the old value.
- Strict versus non-strict comparisons when counting smaller or larger elements, which change prefix(r) to prefix(r - 1).
- Integer overflow in sums and in multiplications such as value times index.
Fenwick Tree (Binary Indexed Tree) Interview Questions: questions with worked answers
1 Implement a Fenwick tree (binary indexed tree)
easyIndex i of the tree stores the sum of the range of length lowbit(i) ending at i, where lowbit(i) = i & -i. Update adds to i and then to i + lowbit(i) until past n. Prefix query sums at i and then at i - lowbit(i) until 0. The structure is 1-indexed, because lowbit(0) is 0 and would never move. Time O(log n) per operation, space O(n). Edge cases: index 0 (must not be used), prefix(0) returns 0, adding negative deltas, n of 1.
pythonclass BIT: def __init__(self, n): self.n = n self.t = [0] * (n + 1) def add(self, i, d): # 1-indexed while i <= self.n: self.t[i] += d i += i & -i def prefix(self, i): s = 0 while i > 0: s += self.t[i] i -= i & -i return s bit = BIT(5) for i, v in enumerate([3, 1, 4, 1, 5], 1): bit.add(i, v) print(bit.prefix(3)) # 8javaclass BIT { final int n; final long[] t; BIT(int n) { this.n = n; t = new long[n + 1]; } void add(int i, long d) { for (; i <= n; i += i & -i) t[i] += d; } long prefix(int i) { long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; } }2 Range sum query with point updates
easyStore the array in a BIT. To set a position to a new value, add the difference between the new and old values. A range sum from l to r is prefix(r) minus prefix(l-1). Keep a copy of the array to know the old values. Time O(log n) per operation, O(n log n) to build naively, space O(n). Edge cases: updating to the same value (delta 0), l equal to 0 in a 0-indexed API (shift by one), negative values.
pythonclass BIT: def __init__(self, n): self.n = n self.t = [0] * (n + 1) def add(self, i, d): # 1-indexed while i <= self.n: self.t[i] += d i += i & -i def prefix(self, i): s = 0 while i > 0: s += self.t[i] i -= i & -i return s class NumArray: def __init__(self, nums): self.a = list(nums) self.b = BIT(len(nums)) for i, v in enumerate(nums, 1): self.b.add(i, v) def update(self, i, val): self.b.add(i + 1, val - self.a[i]) self.a[i] = val def sum_range(self, l, r): return self.b.prefix(r + 1) - self.b.prefix(l)javaclass BIT { final int n; final long[] t; BIT(int n) { this.n = n; t = new long[n + 1]; } void add(int i, long d) { for (; i <= n; i += i & -i) t[i] += d; } long prefix(int i) { long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; } } class NumArray { private final int[] a; private final BIT b; NumArray(int[] nums) { a = nums.clone(); b = new BIT(nums.length); for (int i = 0; i < nums.length; i++) b.add(i + 1, nums[i]); } void update(int i, int val) { b.add(i + 1, val - a[i]); a[i] = val; } int sumRange(int l, int r) { return (int) (b.prefix(r + 1) - b.prefix(l)); } }3 Range update, point query with a difference BIT
mediumKeep a BIT over the difference array. To add v to every element in [l, r], add v at l and subtract v at r+1. The current value at position i is the prefix sum of the differences up to i. Time O(log n) per operation, space O(n). Edge cases: r equal to n (the r+1 update is skipped by the bound check), overlapping updates accumulate, base array values are added separately.
pythonclass BIT: def __init__(self, n): self.n = n self.t = [0] * (n + 1) def add(self, i, d): # 1-indexed while i <= self.n: self.t[i] += d i += i & -i def prefix(self, i): s = 0 while i > 0: s += self.t[i] i -= i & -i return s class RangeAdd: def __init__(self, n): self.n = n self.b = BIT(n + 1) def add(self, l, r, v): # 1-indexed inclusive self.b.add(l, v) self.b.add(r + 1, -v) def get(self, i): return self.b.prefix(i)javaclass BIT { final int n; final long[] t; BIT(int n) { this.n = n; t = new long[n + 1]; } void add(int i, long d) { for (; i <= n; i += i & -i) t[i] += d; } long prefix(int i) { long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; } } class RangeAdd { private final BIT b; RangeAdd(int n) { b = new BIT(n + 1); } void add(int l, int r, long v) { b.add(l, v); b.add(r + 1, -v); } long get(int i) { return b.prefix(i); } }4 Count inversions with a Fenwick tree
mediumCompress values to ranks 1..m. Scan left to right; for each element, the number of earlier elements larger than it is (elements inserted so far) minus prefix(rank). Then insert the rank. This is the standard alternative to merge sort. Time O(n log n), space O(n). Edge cases: duplicates (use prefix(rank) so equal values are not counted), sorted array (0), reversed array needing long, empty input.
pythonclass BIT: def __init__(self, n): self.n = n self.t = [0] * (n + 1) def add(self, i, d): # 1-indexed while i <= self.n: self.t[i] += d i += i & -i def prefix(self, i): s = 0 while i > 0: s += self.t[i] i -= i & -i return s def count_inversions(a): ranks = {v: i for i, v in enumerate(sorted(set(a)), 1)} b = BIT(len(ranks)) inv = 0 for seen, x in enumerate(a): r = ranks[x] inv += seen - b.prefix(r) b.add(r, 1) return invjavaclass BIT { final int n; final long[] t; BIT(int n) { this.n = n; t = new long[n + 1]; } void add(int i, long d) { for (; i <= n; i += i & -i) t[i] += d; } long prefix(int i) { long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; } } long countInversions(int[] a) { int[] sorted = Arrays.stream(a).distinct().sorted().toArray(); BIT b = new BIT(sorted.length); long inv = 0; for (int seen = 0; seen < a.length; seen++) { int r = Arrays.binarySearch(sorted, a[seen]) + 1; inv += seen - b.prefix(r); b.add(r, 1); } return inv; }5 Count of smaller numbers after self
mediumScan from right to left. For each element, the number of strictly smaller elements already inserted is prefix(rank - 1). Record it, then insert the rank. Compression keeps the tree size at the number of distinct values. Time O(n log n), space O(n). Edge cases: duplicates (rank - 1 excludes equals), negative numbers (compress first), single element.
pythonclass BIT: def __init__(self, n): self.n = n self.t = [0] * (n + 1) def add(self, i, d): # 1-indexed while i <= self.n: self.t[i] += d i += i & -i def prefix(self, i): s = 0 while i > 0: s += self.t[i] i -= i & -i return s def count_smaller(nums): ranks = {v: i for i, v in enumerate(sorted(set(nums)), 1)} b = BIT(len(ranks)) res = [0] * len(nums) for i in range(len(nums) - 1, -1, -1): r = ranks[nums[i]] res[i] = b.prefix(r - 1) b.add(r, 1) return resjavaclass BIT { final int n; final long[] t; BIT(int n) { this.n = n; t = new long[n + 1]; } void add(int i, long d) { for (; i <= n; i += i & -i) t[i] += d; } long prefix(int i) { long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; } } List<Integer> countSmaller(int[] nums) { int[] sorted = Arrays.stream(nums).distinct().sorted().toArray(); BIT b = new BIT(sorted.length); Integer[] res = new Integer[nums.length]; for (int i = nums.length - 1; i >= 0; i--) { int r = Arrays.binarySearch(sorted, nums[i]) + 1; res[i] = (int) b.prefix(r - 1); b.add(r, 1); } return Arrays.asList(res); }6 Find the kth smallest using binary lifting on the tree
mediumKeep counts per value in a BIT. To find the smallest index with prefix count at least k, build the answer bit by bit from the highest power of two: advance pos by pw if the tree node at pos + pw has count below k, and subtract it from k. The answer is pos + 1. This avoids an O(log^2 n) binary search over prefix queries. Time O(log n), space O(n). Edge cases: k larger than the total (check first), duplicates (counts above 1), removing values by adding -1.
pythonclass BIT: def __init__(self, n): self.n = n self.t = [0] * (n + 1) def add(self, i, d): # 1-indexed while i <= self.n: self.t[i] += d i += i & -i def prefix(self, i): s = 0 while i > 0: s += self.t[i] i -= i & -i return s def kth(b, k): pos, pw = 0, 1 while pw * 2 <= b.n: pw *= 2 while pw: if pos + pw <= b.n and b.t[pos + pw] < k: pos += pw k -= b.t[pos] pw >>= 1 return pos + 1javaclass BIT { final int n; final long[] t; BIT(int n) { this.n = n; t = new long[n + 1]; } void add(int i, long d) { for (; i <= n; i += i & -i) t[i] += d; } long prefix(int i) { long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; } } int kth(BIT b, long k) { int pos = 0, pw = Integer.highestOneBit(b.n); for (; pw > 0; pw >>= 1) if (pos + pw <= b.n && b.t[pos + pw] < k) { pos += pw; k -= b.t[pos]; } return pos + 1; }7 Range update and range query with two Fenwick trees
hardMaintain two BITs, B1 and B2. To add v on [l, r], update B1 with +v at l and -v at r+1, and B2 with v*(l-1) at l and -v*r at r+1. The prefix sum up to i is sum(B1, i) * i - sum(B2, i). A range sum is the difference of two prefix sums. Time O(log n) per operation, space O(n). Edge cases: r+1 beyond n is ignored by the bound check, long arithmetic for large values times indices, a range that touches position 1.
pythonclass BIT: def __init__(self, n): self.n = n self.t = [0] * (n + 1) def add(self, i, d): # 1-indexed while i <= self.n: self.t[i] += d i += i & -i def prefix(self, i): s = 0 while i > 0: s += self.t[i] i -= i & -i return s class RangeBIT: def __init__(self, n): self.b1, self.b2 = BIT(n), BIT(n) def add(self, l, r, v): # 1-indexed inclusive self.b1.add(l, v); self.b1.add(r + 1, -v) self.b2.add(l, v * (l - 1)); self.b2.add(r + 1, -v * r) def prefix(self, i): return self.b1.prefix(i) * i - self.b2.prefix(i) def range_sum(self, l, r): return self.prefix(r) - self.prefix(l - 1)javaclass BIT { final int n; final long[] t; BIT(int n) { this.n = n; t = new long[n + 1]; } void add(int i, long d) { for (; i <= n; i += i & -i) t[i] += d; } long prefix(int i) { long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; } } class RangeBIT { private final BIT b1, b2; RangeBIT(int n) { b1 = new BIT(n); b2 = new BIT(n); } void add(int l, int r, long v) { b1.add(l, v); b1.add(r + 1, -v); b2.add(l, v * (l - 1)); b2.add(r + 1, -v * r); } long prefix(int i) { return b1.prefix(i) * i - b2.prefix(i); } long rangeSum(int l, int r) { return prefix(r) - prefix(l - 1); } }8 Reverse pairs: count i < j with a[i] > 2 * a[j]
hardScan left to right. For each j, the earlier elements greater than 2*a[j] number (inserted so far) minus the count of inserted values at most 2*a[j]. Compress only the original values, and use binary search to map 2*a[j] to a rank. Use long for the doubling. Time O(n log n), space O(n). Edge cases: doubling overflow (cast to long), negative numbers, duplicates, equal values do not count since the comparison is strict.
pythonclass BIT: def __init__(self, n): self.n = n self.t = [0] * (n + 1) def add(self, i, d): # 1-indexed while i <= self.n: self.t[i] += d i += i & -i def prefix(self, i): s = 0 while i > 0: s += self.t[i] i -= i & -i return s from bisect import bisect_right def reverse_pairs(a): vals = sorted(set(a)) b = BIT(len(vals)) total = 0 for seen, x in enumerate(a): k = bisect_right(vals, 2 * x) # values <= 2x occupy ranks 1..k total += seen - b.prefix(k) b.add(bisect_right(vals, x), 1) return totaljavaclass BIT { final int n; final long[] t; BIT(int n) { this.n = n; t = new long[n + 1]; } void add(int i, long d) { for (; i <= n; i += i & -i) t[i] += d; } long prefix(int i) { long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; } } long reversePairs(int[] a) { long[] vals = Arrays.stream(a).asLongStream().distinct().sorted().toArray(); BIT b = new BIT(vals.length); long total = 0; for (int seen = 0; seen < a.length; seen++) { int k = upper(vals, 2L * a[seen]); total += seen - b.prefix(k); b.add(upper(vals, a[seen]), 1); } return total; } private int upper(long[] v, long x) { // count of values <= x int lo = 0, hi = v.length; while (lo < hi) { int mid = (lo + hi) >>> 1; if (v[mid] <= x) lo = mid + 1; else hi = mid; } return lo; }9 Two-dimensional Fenwick tree: submatrix sums with point updates
hardNest the one-dimensional update and query loops. Update adds delta at (r, c) by looping rows i += i & -i and, inside, columns j += j & -j. A prefix query sums the rectangle from the origin; a submatrix sum uses inclusion-exclusion over four prefix queries. Time O(log m * log n) per operation, space O(m * n). Edge cases: 1-based internal indexes, inclusion-exclusion order of the four terms, update by delta not by value.
pythonclass BIT2D: def __init__(self, m, n): self.m, self.n = m, n self.t = [[0] * (n + 1) for _ in range(m + 1)] self.a = [[0] * n for _ in range(m)] def update(self, r, c, val): # 0-indexed d, self.a[r][c] = val - self.a[r][c], val i = r + 1 while i <= self.m: j = c + 1 while j <= self.n: self.t[i][j] += d j += j & -j i += i & -i def _pre(self, r, c): # sum of rows < r, cols < c s, i = 0, r while i > 0: j = c while j > 0: s += self.t[i][j] j -= j & -j i -= i & -i return s def region(self, r1, c1, r2, c2): return (self._pre(r2 + 1, c2 + 1) - self._pre(r1, c2 + 1) - self._pre(r2 + 1, c1) + self._pre(r1, c1))javaclass BIT2D { private final int m, n; private final int[][] t, a; BIT2D(int m, int n) { this.m = m; this.n = n; t = new int[m + 1][n + 1]; a = new int[m][n]; } void update(int r, int c, int val) { int d = val - a[r][c]; a[r][c] = val; for (int i = r + 1; i <= m; i += i & -i) for (int j = c + 1; j <= n; j += j & -j) t[i][j] += d; } private int pre(int r, int c) { int s = 0; for (int i = r; i > 0; i -= i & -i) for (int j = c; j > 0; j -= j & -j) s += t[i][j]; return s; } int region(int r1, int c1, int r2, int c2) { return pre(r2 + 1, c2 + 1) - pre(r1, c2 + 1) - pre(r2 + 1, c1) + pre(r1, c1); } }10 Number of distinct values in range queries (offline)
hardSort the queries by right endpoint and sweep i from left to right. Keep a BIT with a 1 at the last occurrence position of each value seen so far: when a value reappears, remove the 1 at its previous position and put one at i. For a query (l, r) answered at i = r, the number of distinct values is prefix(r) - prefix(l-1). Time O((n + q) log n), space O(n + q). Edge cases: must be answered offline (sorted), 1-indexed positions, queries that share a right endpoint, value ranges needing a map.
pythonclass BIT: def __init__(self, n): self.n = n self.t = [0] * (n + 1) def add(self, i, d): # 1-indexed while i <= self.n: self.t[i] += d i += i & -i def prefix(self, i): s = 0 while i > 0: s += self.t[i] i -= i & -i return s def distinct_in_ranges(a, queries): # queries: list of (l, r), 1-indexed inclusive n = len(a) b = BIT(n) last = {} by_r = [[] for _ in range(n + 1)] for qi, (l, r) in enumerate(queries): by_r[r].append((l, qi)) ans = [0] * len(queries) for i in range(1, n + 1): v = a[i - 1] if v in last: b.add(last[v], -1) b.add(i, 1) last[v] = i for l, qi in by_r[i]: ans[qi] = b.prefix(i) - b.prefix(l - 1) return ansjavaclass BIT { final int n; final long[] t; BIT(int n) { this.n = n; t = new long[n + 1]; } void add(int i, long d) { for (; i <= n; i += i & -i) t[i] += d; } long prefix(int i) { long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; } } int[] distinctInRanges(int[] a, int[][] queries) { int n = a.length; BIT b = new BIT(n); Map<Integer, Integer> last = new HashMap<>(); List<List<int[]>> byR = new ArrayList<>(); for (int i = 0; i <= n; i++) byR.add(new ArrayList<>()); for (int qi = 0; qi < queries.length; qi++) byR.get(queries[qi][1]).add(new int[]{queries[qi][0], qi}); int[] ans = new int[queries.length]; for (int i = 1; i <= n; i++) { Integer prev = last.put(a[i - 1], i); if (prev != null) b.add(prev, -1); b.add(i, 1); for (int[] q : byR.get(i)) ans[q[1]] = (int) (b.prefix(i) - b.prefix(q[0] - 1)); } return ans; }
Frequently asked questions
Why is it called a binary indexed tree?
Each index covers a range whose length is the lowest set bit of the index, so the binary representation of the index decides which ranges are combined in a query.
Fenwick tree or segment tree?
Choose a Fenwick tree for sums and counts because it is simpler and faster. Choose a segment tree for min, max, lazy range updates or descents that need more than prefix sums.
How do I build a Fenwick tree in O(n)?
Copy the array into the tree, then for each i add t[i] to its parent at i + (i & -i) when that is within n. This avoids n separate O(log n) updates.
Where do Fenwick trees appear in interviews?
Mostly as the efficient solution to counting problems such as inversions or count of smaller numbers after self. See how to crack technical interviews for how follow-up optimisation questions are handled.
Related guides
More in DSA Interview Questions
- Graph Interview Questions and Answers
- Greedy algorithm interview questions with worked solutions
- Grid and Matrix DP Interview Questions
- Hashing interview questions with worked solutions
- Heap and Priority Queue Interview Questions
- Interval DP Interview Questions
- Interval interview questions with worked solutions
- Kadane algorithm interview questions with worked solutions
- KMP and string matching interview questions with solutions
- Knapsack DP Interview Questions
- Linked list interview questions with worked solutions
- Longest Common Subsequence (LCS) Interview Questions