🧭 Conceptual Foundation & Pattern Intuition

A prefix-sum array answers range sums in $O(1)$ but needs an $O(N)$ rebuild after every change; a plain array updates in $O(1)$ but sums in $O(N)$. A Fenwick tree (Binary Indexed Tree) meets in the middle: both operations take $O(\log N)$. Slot tree[i] stores the sum of a block of positions that ends at i and is i & (-i) long (the value of i's lowest set bit).

🏟️ The Analogy: Receipts Filed by Month, Quarter and Year

An accountant keeps receipts in folders of different sizes: some cover one month, some two, some four, some eight, each ending at a certain month. To total January to November, you add a handful of folders that together cover exactly those months. When a March receipt is corrected, you fix every folder that contains March: a handful again.

🪄 The Mathematical Harmony / Magic Trick

def query(self, i):          # sum of positions 1..i
    total = 0
    while i > 0:
        total += self.tree[i]
        i -= i & (-i)        # jump to just before this block
    return total
 
def update(self, i, delta):  # add delta at position i
    while i <= self.n:
        self.tree[i] += delta
        i += i & (-i)        # jump to the next block that also contains i
 

Removing the lowest set bit lands just before the block tree[i] covers, so the blocks query adds never overlap and cover exactly 1..i. Adding it reaches the next bigger block that contains i. Both loops touch one block per bit: $O(\log N)$.

💡 Summary

The tree is 1-indexed: i & (-i) is 0 when i is 0, so position 0 would never move. NumArray shifts every index up by one, keeps the current values to turn "set to val" into "add val - old", and answers sumRange(left, right) as query(right + 1) - query(left).