Fenwick Tree Interview Questions: Indexing, Prefix Queries, and Order Statistics

A Fenwick tree is the right interview tool when an array changes and you must repeatedly ask for cumulative counts or sums. It gives a point update and a prefix query in O(log n) using one compact array. The catch is that a memorized loop is easy to break: most incorrect answers mix a caller's 0-based index with the tree's 1-based invariant, or use the wrong strictness when turning a cumulative total back into an index.

This guide then takes the useful follow-ups further: explain what each tree cell represents, convert inclusive ranges safely, and find the first prefix that crosses a target. Those are practice patterns, not a prediction of any specific employer's questions.

Fenwick Tree Interview Questions: Quick Answer

Say that a Fenwick tree, also called a Binary Indexed Tree (BIT), stores partial cumulative totals in a 1-based array. It supports add(index, delta) and prefix(end) in O(log n), so an inclusive range sum is prefix(right) - prefix(left - 1). It is a strong fit for point updates plus associative prefix aggregates such as counts or sums.

The original 1994 paper introduced the structure for dynamic cumulative frequency tables and derives its traversal from the binary representation of an index. The important interview insight is therefore not “it is a tree.” It is that each slot owns a power-of-two suffix ending at its index, so a few bit operations jump across exactly the blocks needed for an update or a prefix total.

When a Fenwick tree is the right choice

First state the operation mix. A static prefix array wins when values never change: build once in O(n), then answer each range sum in O(1). Once a value changes, every later prefix becomes stale, so repairing that array costs O(n) in the worst case.

Need	Recommended first choice	Why
Static sums over an array	Prefix array	Lowest complexity; range sum is two reads.
Point add/update plus prefix or range sums	Fenwick tree	Compact O(log n) updates and prefix queries.
General range aggregate, range update, or custom merge	Segment tree	More flexible, with more code and constants.
Repeated min/max element only	Heap or monotonic structure	It does not need prefix totals.

This table is a design inference, not an employer rule. Ask whether the update is a delta or an assignment, whether the aggregate has an inverse, and whether queries are prefixes, arbitrary ranges, or order statistics. A Fenwick tree can represent an assignment by first reading the current value and applying new_value - old_value; it does not magically know the old value without separate storage or a recoverable difference.

The invariant behind lowbit

A Fenwick tree uses internal positions 1..n. Define lowbit(i) = i & -i: it isolates the least significant set bit. In a sum tree, tree[i] holds the sum of the final lowbit(i) values ending at i.

Internal index	Binary	lowbit	Range represented
1	0001	1	[1, 1]
2	0010	2	[1, 2]
3	0011	1	[3, 3]
4	0100	4	[1, 4]
6	0110	2	[5, 6]

For prefix(6), add tree[6], then clear its least-significant set bit to reach 4, add tree[4], and stop at zero. The covered blocks [5,6] and [1,4] are disjoint and exactly form [1,6].

For an update at position 5, add the delta to tree[5], then jump to 6, then 8, because each of those represented ranges contains position 5. The two loops are opposites: a query removes a low bit to find preceding disjoint blocks; an update adds that low bit to find containing blocks.

Keep the public index 0-based and the tree 1-based

Most interview inputs use nums[0]. Do not force callers to remember a second convention. Translate exactly once at the public boundary: internal position p = external_index + 1.

class Fenwick:
    def __init__(self, n: int):
        self.n = n
        self.tree = [0] * (n + 1)  # tree[0] is deliberately unused

    def add(self, index: int, delta: int) -> None:
        p = index + 1
        while p <= self.n:
            self.tree[p] += delta
            p += p & -p

    def prefix(self, end: int) -> int:
        # sum of external indexes [0, end), so end may be 0
        total = 0
        p = end
        while p > 0:
            total += self.tree[p]
            p -= p & -p
        return total

    def range_sum(self, left: int, right: int) -> int:
        # inclusive caller contract
        if not 0 <= left <= right < self.n:
            raise IndexError("invalid inclusive range")
        return self.prefix(right + 1) - self.prefix(left)

The naming matters. Here prefix(end) deliberately uses an exclusive external endpoint, so it needs no +1 inside. A different valid design exposes prefix(index) as an inclusive query and translates inside. Mixing the two is the source of the classic off-by-one bug. State the contract before coding and test it with a one-element array. As a quick checksum, after adding [4], prefix(0) must be zero and range_sum(0, 0) must be four.

Turn point updates into range queries

Suppose nums = [1, 3, 5]. Build the tree with three add calls. range_sum(0, 2) is 9. If update(1, 2) means assignment, retain nums, compute delta = 2 - nums[1], replace nums[1], and call add(1, delta). The next range sum is 8.

A candidate-reported practice record can motivate a drill, but it does not prove that Moloco or any other employer asks the same wording today.

One follow-up changes the data structure: range-add plus point-query can use a difference array stored in a Fenwick tree. Range-add plus range-sum uses two trees and a derived prefix formula. Mention the extension only after confirming the operation contract. Using a single point-update tree for arbitrary interval updates is a confident but wrong answer.

Order statistics: find the first prefix above a target

The most valuable follow-up uses non-negative frequencies. Given a target t with 0 <= t < total, find the smallest 0-based index whose cumulative frequency is strictly greater than t. This maps a weighted random draw to its owning interval and finds the (t + 1)-th item in a frequency multiset.

The 1996 follow-up on frequency-to-symbol lookup exposes an important condition: prefix search relies on a monotone cumulative total. Negative frequencies make prefixes fall and invalidate the binary walk. Zero frequencies are valid, but they own empty intervals.

def first_prefix_gt(bit: Fenwick, target: int) -> int:
    if target < 0 or target >= bit.prefix(bit.n):
        raise ValueError("target is outside total frequency")

    pos = 0                 # internal prefix with sum <= target
    step = 1 << (bit.n.bit_length() - 1)
    while step:
        candidate = pos + step
        if candidate <= bit.n and bit.tree[candidate] <= target:
            target -= bit.tree[candidate]
            pos = candidate
        step >>= 1
    return pos              # next internal position is pos + 1; external index is pos

The strictness is the proof. The loop advances only across blocks whose cumulative contribution is <= target, so it ends at the greatest prefix that does not cross the target. The next element is the first one that does. If you instead need the first prefix >= rank for a 1-based rank, begin with rank and use the analogous < rank test. Do not casually swap those inequalities: it changes behavior at exact cumulative boundaries.

Dynamic weighted sampling adds ID compression and deletes, which are useful tests of whether you can separate an external key from its dense tree position.

Coordinate compression is often the hidden first step

A Fenwick tree indexes a dense integer domain. Array positions already have one. Values such as -10^9, 17, and 10^12 do not. For count-smaller, inversion, or rank problems, sort the distinct values and map each to a rank in 1..k internally.

The candidate-reported movie-ratings, array, and release-scheduler practice question uses this pattern for “count smaller numbers after self”: scan right to left, query prefix(rank - 1) for strictly smaller values already seen, then add one at rank. The rank - 1 is not decoration. Querying rank would include equal values and solve a different problem.

Coordinate compression preserves ordering, not distance. It is correct when the data structure needs order or frequency by value; it is not correct when the numeric gap itself is part of the answer.

Five mistakes worth testing before you explain the solution

1. Index zero loops forever. Calling an internal update with p = 0 makes p += p & -p stay at zero. Translate external index zero to internal one.
2. A range endpoint changes meaning. Test range_sum(0, 0), range_sum(0, n - 1), and adjacent ranges. Decide whether prefixes are inclusive or exclusive once.
3. Assignment is treated as addition. Apply two assignments to the same index and verify that the old value does not remain in the total.
4. Duplicate ranks use the wrong comparison. “Strictly smaller” queries rank - 1; “smaller or equal” queries rank.
5. Prefix search accepts negative counts. It has no monotonic cumulative order to search. Validate frequency updates and reject an all-zero sampling total.

Practice the explanation, not only the loops

Question	Drill	What to explain aloud
Support Dynamic Range Sums	Point update plus inclusive range sum	Why two prefix calls form one range.
Generate Weighted Random NFTs with Updates	Prefix search over mutable weights	Why the target uses first cumulative weight > r.
Design Dynamic Weighted Random Sampling with Updates	Dense ranks, insertion, deletion	How external IDs map to stable tree positions.
Solve Three Algorithmic Tasks in Python	Range add and range sum	Why one tree is insufficient for this follow-up.
Solve Movie Ratings, Array, Release Scheduler	Count smaller after self	Why compression and rank - 1 enforce strictness.

Final takeaway

Fenwick tree interview questions reward precise contracts more than clever syntax. Start with the operation mix, keep external indexes 0-based and storage 1-based, state what every tree[i] covers, and make the prefix-search inequality explicit. Then you can move naturally from dynamic range sums to frequency ranks and weighted choices without changing the central invariant.

After each solution, explain a boundary case before looking at the written answer; that is the fastest way to discover whether you understand the structure or only remember its loops.

Sources and Further Reading

• Peter M. Fenwick, A new data structure for cumulative frequency tables (1994)
• Peter M. Fenwick, improved frequency-to-symbol algorithm (1996)

Research note: The technical sources were checked on September 12, 2026. The primary papers establish the data-structure mechanism.