1. The range each tree entry covers

The Fenwick tree numbers the array positions from 1, so position index of nums is $i = \text{index} + 1$. Write $\text{low}(i)$ for the value of the lowest 1 bit of $i$. For example, $6$ is 110 in binary, so $\text{low}(6) = 2$.

Entry tree[i] holds the sum of $\text{low}(i)$ values: the positions from $i - \text{low}(i) + 1$ to $i$. Written as a half-open range, it covers $(i - \text{low}(i),\ i]$.

2. Why i & -i is the lowest 1 bit

In two's complement, $-i$ is computed as "flip every bit of $i$, then add 1". Say $i$ ends with a 1 followed by $k$ zeros. Flipping gives a 0 followed by $k$ ones. Adding 1 turns those $k$ ones back into zeros and the 0 into a 1. So $-i$ has the same lowest 1 bit as $i$, with the same $k$ zeros after it. Every bit to the left of it is flipped.

& keeps a bit only where both numbers have a 1. Only the lowest 1 bit is 1 in both. So i & -i equals $\text{low}(i)$. For $i = 6$: in 8 bits, $6$ is 00000110 and $-6$ is 11111010, and their & is 00000010, which is 2.

3. Why a query and an update each touch about $\log n$ entries

A prefix sum walks down. query(i) adds tree[i], which covers $(i - \text{low}(i), i]$. Then it sets $i \leftarrow i - \text{low}(i)$ and repeats. The next range ends exactly where the last one started. So the ranges fit together without gaps or overlaps, and they cover $(0, i]$. Each step clears the lowest 1 bit of $i$, so the loop runs once per 1 bit, at most $\log_2 n + 1$ times. For $i = 7$ the ranges are $(6, 7]$, $(4, 6]$ and $(0, 4]$.

An update walks up. A change at position $i$ must reach every entry whose range contains $i$. update(i, delta) adds delta to tree[i], then sets $i \leftarrow i + \text{low}(i)$ and repeats. Adding the lowest 1 bit moves to the next larger entry whose range still reaches down to position $i$. Each step makes the lowest 1 bit at least twice as large, so the loop runs at most $\log_2 n + 1$ times. With $n = 8$, a change at position 3 visits entries 3, 4 and 8. The table of part 1 shows that these are exactly the entries that cover position 3.

A range sum is the difference of two prefix sums, as for a fixed array:

$\text{sum}(\text{left} \ldots \text{right}) = \text{query}(\text{right}) - \text{query}(\text{left} - 1)$

with 1-based positions. sumRange adds 1 to both indices first.

4. The 1-based positions and the size of the change

Position 0 does not work in a Fenwick tree. $\text{low}(0) = 0$, so update(0, ...) would add 0 to $i$ forever. That is why the code stores position index at $i = \text{index} + 1$, and why tree has $n + 1$ entries with tree[0] unused. For query(0), the loop while i > 0 runs zero times and returns 0, which is the sum of no elements.

The tree stores sums, so it must receive the change of a value, not the new value. NumArray.update sends val - self.nums[index], and then stores val in self.nums for the next change. Sending val itself would add the new value on top of the old one.

5. Example 1 by hand

nums = [1, 3, 5], so $n = 3$. The constructor calls update once per value:

So tree[2] = 4 holds positions 1 and 2, and tree[3] = 5 holds position 3 alone.

sumRange(0, 2) computes query(3) - query(0). query(3) adds tree[3] = 5, moves to $3 - 1 = 2$, adds tree[2] = 4, and moves to $2 - 2 = 0$. It returns $9$. query(0) returns 0. The answer is $9$, the expected output.

update(1, 2) changes nums[1] from 3 to 2, so it sends the change $2 - 3 = -1$ to position 2. Entry 2 becomes $4 - 1 = 3$. The next entry would be $2 + 2 = 4$, past $n = 3$, so the update stops.

The second sumRange(0, 2) adds tree[3] = 5 and tree[2] = 3, and returns $8$, the expected output.

6. From the math to the code

Both walks take $O(\log n)$ steps. The constructor calls update $n$ times, so it takes $O(n \log n)$ time. The tree and the copy of nums take $O(n)$ space.