From prefix to range
A Fenwick tree gives you prefix sums: the total from the start up to some index. To get the sum of an arbitrary slice from left to right, subtract the prefix up to just before left from the prefix up to right. Two prefix queries, one subtraction, and you have any range sum.
Range update with a difference idea
The same structure can flip its roles. If you instead store a difference array inside the Fenwick tree, you can add a value to a whole range by touching only two positions: add the value at the left boundary and subtract it just past the right boundary. A prefix sum of this difference array then recovers the current value at any single point.
Choosing the variant
- Point update, range query: store values directly, query by subtracting prefixes. Good when individual cells change and you ask for slice totals.
- Range update, point query: store differences, update two endpoints, query a prefix. Good when whole ranges shift and you ask for one cell.
A two BIT combination even supports range update with range query, layering the difference idea twice.
Why it is efficient
Each variant is still just prefix sums under the hood, so every operation remains logarithmic while the array stays compact.
Key idea
Any range sum is the difference of two prefix sums, and storing differences lets a Fenwick tree apply a range update by changing just two endpoints.