Fenwick Tree: Binary Indexed Prefix Sum Pattern

Learning Outcome

After this lesson, you should be able to use the lowest set bit to jump between responsible prefix buckets.

Problem Statement

Design a Fenwick tree with add(index,delta), sum(index), and rangeSum(left,right).

Brute Force Approach

After every point update, update all later prefix sums. This makes each update O(n).

Optimized Approach

Use a 1-indexed binary indexed tree. For update, jump upward with index += index & -index. For query, jump downward with index -= index & -index.

Exact Pseudocode

add(index, delta):
  while index is at most n:
    bit[index] += delta
    index += index & -index

sum(index):
  answer = 0
  while index is greater than 0:
    answer += bit[index]
    index -= index & -index
  return answer

rangeSum(left, right):
  return sum(right) - sum(left - 1)
  

Reference Code

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, index, delta):
        while index <= self.n:
            self.bit[index] += delta
            index += index & -index

    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.bit[index]
            index -= index & -index
        return answer

    def rangeSum(self, left, right):
        return self.sum(right) - self.sum(left - 1)
  

Sample Dry Run

Complexity

Edge Cases

• Fenwick code is usually 1-indexed.
• Calling add with index 0 can loop forever if not guarded or converted.
• rangeSum(left,right) uses prefix subtraction.

Interview Checklist

• Use index & -index to get the lowest set bit.
• Update moves upward; query moves downward.
• Convert 0-indexed user input carefully if needed.

FAQs

The lowest-set-bit jump needs index 0 to be avoided because it cannot advance.

Sum from left to right equals prefix(right) minus prefix(left

• 1).

Binary indexed prefix buckets.