Fenwick Tree

A fitness app keeps one step count per day. Old days sometimes get corrected, and users ask for the total over any stretch of days. Both must stay fast, even for years of data. Build a FenwickTree class (any structure that meets the speed target is fine):

• FenwickTree(nums) starts from the list of whole numbers nums.
• set(i, value) changes the number at index i to value.
• range_sum(left, right) returns the sum of the current numbers in the slice [left:right]: index left is included and index right is not, as in Python slicing. When left == right the sum is 0.

Both methods should take about log n steps, where n = len(nums).

Examples

ft = FenwickTree([5, 2, 7, 1, 3])
ft.range_sum(0, 5)    # returns 18
ft.range_sum(1, 4)    # returns 10    (2 + 7 + 1)
ft.set(2, 0)
ft.range_sum(1, 4)    # returns 3
ft.range_sum(3, 3)    # returns 0

Constraints

• 1 <= len(nums) <= 100,000; all numbers, old and new, are whole numbers between -10^9 and 10^9
• 0 <= i < len(nums) and 0 <= left <= right <= len(nums)
• Up to 40,000 calls in total. Adding up the slice on every call, or rebuilding a table of running totals after every change, is too slow at that size.