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).
| Input | Output | Why |
|---|---|---|
add(1,5), add(3,7), sum(3) | 12 | The prefix through index 3 includes the added values 5 and 7. |
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
| Step | State | Result |
|---|---|---|
| add 1,5 | update bit[1], bit[2], bit[4] | responsible buckets get +5 |
| add 3,7 | update bit[3], bit[4] | buckets covering index 3 get +7 |
| sum 3 | read bit[3], then bit[2] | 7 + 5 = 12 |
| rangeSum | sum(right) minus sum(left | range answer |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(log n) per update or query | Each jump removes or adds the lowest set bit, so only logarithmic buckets are touched. |
| Space | O(n) | The tree stores one compact bucket array. |
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
Why is Fenwick usually 1-indexed?
The lowest-set-bit jump needs index 0 to be avoided because it cannot advance.
How is range sum built from prefix sums?
Sum from left to right equals prefix(right) minus prefix(left
- 1).
What is the core pattern?
Binary indexed prefix buckets.