Autocoder

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 queryO(log n)
Memoryn + 1 numbers
Indexing1-based, via i & -i
LimitsNeeds 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

Fenwick Tree (Binary Indexed Tree) Interview Questions: questions with worked answers

  1. 1

    Implement a Fenwick tree (binary indexed tree)

    easy

    Index 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.

    python
    class 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))   # 8
    java
    class 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. 2

    Range sum query with point updates

    easy

    Store 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.

    python
    class 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)
    java
    class 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. 3

    Range update, point query with a difference BIT

    medium

    Keep 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.

    python
    class 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)
    java
    class 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. 4

    Count inversions with a Fenwick tree

    medium

    Compress 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.

    python
    class 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 inv
    java
    class 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. 5

    Count of smaller numbers after self

    medium

    Scan 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.

    python
    class 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 res
    java
    class 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. 6

    Find the kth smallest using binary lifting on the tree

    medium

    Keep 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.

    python
    class 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 + 1
    java
    class 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. 7

    Range update and range query with two Fenwick trees

    hard

    Maintain 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.

    python
    class 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)
    java
    class 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. 8

    Reverse pairs: count i < j with a[i] > 2 * a[j]

    hard

    Scan 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.

    python
    class 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 total
    java
    class 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. 9

    Two-dimensional Fenwick tree: submatrix sums with point updates

    hard

    Nest 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.

    python
    class 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))
    java
    class 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. 10

    Number of distinct values in range queries (offline)

    hard

    Sort 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.

    python
    class 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 ans
    java
    class 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

See all in this section