Binary Indexed Tree

https://leetcode.com/problems/range-sum-query-mutable/

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.
Example:
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

This problem can be surely solved by segment tree. However, another approach is to use binary indexed tree. Binary indexed tree also provides O(logN) time for lookup, O(logN) update. But it is easier to implement and takes O(N) storage.

Let’s start by talking about a bit operation. For example, if we have a = 00110100 in binary, and we want to get the as much as zero from right until it reaches the 1st 1, which is 100. We can do (-a) & a. It is because in machine, all number uses complement form. It has below calculation:
complement of a:   00110100
complement of -a:  11001100
So (-a) & a = 100

Let’s see an example of binary indexed tree for index 1 to 15. Assume we built an binary indexed tree for nums[] array.

In this tree structure, take 1011(11) as example. The value of tree[11] contains nums[11]. In order to get the rangeSum(1, 11), we just add value of its ancestry: tree[11] + tree[10] + tree[8].

tree[10] contains nums[9], nums[10]; tree[8] contains value nums[1], nums[2], nums[3],…,nums[8].

rangeSum(1, 11) = tree[1011] + tree[1010] + tree[1000].

Another example, rangeSum(1, 7) = tree[0111] + tree[0110] + tree[0100]

So, we can find the rule for sum:

while (idx > 0) {
    sum += tree[idx];
    idx -= (-idx) & idx;
}

Let’s talk about how do we updat. Let’s say we increase 2 to nums[5]. Then we should increase 2 to tree[0101], tree[0110], tree[1000]. Another example, we want to add 2 to nums[9], then we need to add 2 to tree[1001], tree[1010], tree[1000]. So we can find the rule for increase a value to nums[idx]:

while (idx <= n) {
    tree[idx] += val;
    idx += (-idx) & idx;
}

check my code on github: link