How Do You Implement a Fenwick Tree for Dynamic Prefix Sums and Weighted Selection?

1. Question

You have a dynamic frequency table of length n. Values at positions are frequently increased, and the system must answer prefix sums, range sums, and locate the position containing the k-th unit of cumulative weight. Implement a Fenwick Tree (Binary Indexed Tree) with O(log n) point updates and prefix queries, and compare it with a plain prefix array and a segment tree.

2. Constraints and clarifications

• Use one-based indexing internally; a public API may accept zero-based positions but must convert exactly once.
• Updates may be deltas or differences from a new value; state whether negative values are allowed.
• Ranks start at 1. Weighted selection is defined only when all weights are non-negative and the total is at least k.
• Discuss the single-threaded structure first; concurrent updates need a lock or sharding and cannot assume ordinary integer writes form a consistent snapshot.

3. Core idea

Entry i stores the sum of a contiguous range whose length is lowbit(i) = i & -i. A prefix query repeatedly subtracts lowbit, while a point update repeatedly adds lowbit, so each touches O(log n) array positions. A range sum is the difference of two prefixes. When the initial array is known, propagate each value to its parent index to build in O(n).

4. Reference implementation

class Fenwick:
  init(values):
    tree = [0] * (len(values) + 1)
    for i from 1 to len(values):
      tree[i] += values[i - 1]
      parent = i + lowbit(i)
      if parent < len(tree):
        tree[parent] += tree[i]

  add(index0, delta):
    i = index0 + 1
    while i < len(tree):
      tree[i] += delta
      i += lowbit(i)

  prefixSum(index0Exclusive):
    total = 0
    i = index0Exclusive
    while i > 0:
      total += tree[i]
      i -= lowbit(i)
    return total

  rangeSum(left0, right0Exclusive):
    return prefixSum(right0Exclusive) - prefixSum(left0)

For weighted selection, probe from the highest binary step. If moving to the candidate index keeps the cumulative sum below k, accept that step and subtract its sum from k; the final index plus one is the position containing rank k. This requires monotonic cumulative sums and therefore cannot be used directly with negative weights.

5. Complexity and trade-offs

A Fenwick Tree uses an O(n) array. Point addition, prefix sums, and weighted selection are O(log n), while linear construction is O(n). It is more compact and often has smaller constants than a segment tree, but it naturally expresses reversible prefix aggregates rather than range minima, complex range updates, or rich segment metadata. For read-only data, a plain prefix array answers queries in O(1); Fenwick becomes valuable when updates are frequent.

6. Verification and observability

• Compare every add, prefixSum, and rangeSum with a naive array on random inputs, including empty, singleton, and last-index cases.
• Test all zeros, very large weights, a total exactly equal to k, out-of-range k, and invalid indices.
• Cross-check linear construction against repeated point additions and compare both internal arrays and query results.
• Generate non-negative random weights for weighted selection and check prefix boundaries for every k; reject negative-weight input separately.

7. Common mistakes

• Mixing zero-based and one-based indices so position zero is skipped or the last position overflows.
• Treating i & -i as a negation trick without explaining that it extracts the lowest binary block.
• Using weighted selection with negative values even though cumulative sums are no longer monotonic.
• Overwriting a tree node with the new value instead of adding the delta along the update path.

8. Interview scoring points

Explains lowbit and range coverage

The candidate should state which contiguous range each node stores and why queries and updates follow lowbit jumps.

Writes an implementation without boundary errors

The answer should keep one-based internal indexing, handle empty arrays, invalid positions, and half-open ranges, and never access beyond the array end.

Derives complexity and construction

The candidate should give O(log n) query, update, and selection costs, O(n) linear construction, and compare the boundaries of prefix arrays and segment trees.

Recognizes weighted-selection preconditions

The answer should require non-negative weights and monotonic cumulative sums, then test exact hits, overflow, and large-number boundaries.