# Java using Binary Indexed Tree with clear explanation

• This is to share the explanation of the BIT and the meaning of the bit operations.

``````public class NumArray {
/**
* Binary Indexed Trees (BIT or Fenwick tree):
* https://www.topcoder.com/community/data-science/data-science-
* tutorials/binary-indexed-trees/
*
* Example: given an array a[0]...a[7], we use a array BIT[9] to
* represent a tree, where index [2] is the parent of [1] and [3], [6]
* is the parent of [5] and [7], [4] is the parent of [2] and [6], and
* [8] is the parent of [4]. I.e.,
*
* BIT[] as a binary tree:
*            ______________*
*            ______*
*            __*     __*
*            *   *   *   *
* indices: 0 1 2 3 4 5 6 7 8
*
* BIT[i] = ([i] is a left child) ? the partial sum from its left most
* descendant to itself : the partial sum from its parent (exclusive) to
* itself. (check the range of "__").
*
* Eg. BIT[1]=a[0], BIT[2]=a[1]+BIT[1]=a[1]+a[0], BIT[3]=a[2],
* BIT[4]=a[3]+BIT[3]+BIT[2]=a[3]+a[2]+a[1]+a[0],
* BIT[6]=a[5]+BIT[5]=a[5]+a[4],
* BIT[8]=a[7]+BIT[7]+BIT[6]+BIT[4]=a[7]+a[6]+...+a[0], ...
*
* Thus, to update a[1]=BIT[2], we shall update BIT[2], BIT[4], BIT[8],
* i.e., for current [i], the next update [j] is j=i+(i&-i) //double the
* last 1-bit from [i].
*
* Similarly, to get the partial sum up to a[6]=BIT[7], we shall get the
* sum of BIT[7], BIT[6], BIT[4], i.e., for current [i], the next
* summand [j] is j=i-(i&-i) // delete the last 1-bit from [i].
*
* To obtain the original value of a[7] (corresponding to index [8] of
* BIT), we have to subtract BIT[7], BIT[6], BIT[4] from BIT[8], i.e.,
* starting from [idx-1], for current [i], the next subtrahend [j] is
* j=i-(i&-i), up to j==idx-(idx&-idx) exclusive. (However, a quicker
* way but using extra space is to store the original array.)
*/

int[] nums;
int[] BIT;
int n;

public NumArray(int[] nums) {
this.nums = nums;

n = nums.length;
BIT = new int[n + 1];
for (int i = 0; i < n; i++)
init(i, nums[i]);
}

public void init(int i, int val) {
i++;
while (i <= n) {
BIT[i] += val;
i += (i & -i);
}
}

void update(int i, int val) {
int diff = val - nums[i];
nums[i] = val;
init(i, diff);
}

public int getSum(int i) {
int sum = 0;
i++;
while (i > 0) {
sum += BIT[i];
i -= (i & -i);
}
return sum;
}

public int sumRange(int i, int j) {
return getSum(j) - getSum(i - 1);
}
}

// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);``````

• The explanation is so clear, thanks for your sharing, it is a brilliant method.

• Best explanation so far, thank you so much

• Similiar C++ implementation based others' posts.

I have refered to the post from GeekForGeek

http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

I think the key points are that you should set "i++" and understand the relationship of the children and parents.

`````` class NumArray {
private:
vector<int> _nums;
vector<int> bit;

int lower_bit(int i){
return i&-i;
}

int query(int i){
i++;
int sum=0;
while(i>0){
sum+=bit[i];
i-=lower_bit(i);
}
return sum;
}

void add(int i, int val){
i++;
while(i<bit.size()){
bit[i]+=val;
i+=lower_bit(i);
}
}

public:
NumArray(vector<int> &nums) : _nums(nums) {
bit.resize(nums.size()+1);
for(int i=0; i<nums.size(); i++){
add(i, nums[i]);
}
}

void update(int i, int val) {
if(val!=_nums[i]){
add(i, val-_nums[i]);
_nums[i]=val;
}
}

int sumRange(int i, int j) {
return query(j)-query(i-1);
}
};
``````

• @rikimberley Do you have any idea that why we need to do `y += y & (-y)` to update?

Here is my understanding so far.

I know `x & (-x)` gets the LSB (least significant bit).

I know that index `x` manages the sum in the range `[x - x & (-x), x - 1]`.

So whenever index `y` gets update, we need to update all indices `x` such that `x - x & (-x) <= y <= x - 1`. However, I don't know how to solve this in-equation. I know the answer is: `y + y & (-y)`, and continue. But why?

• range

Hi,

Solving the inequality the you gave is not easy, but you can view in a different angle. That is, once an index (of BIT array) [y] is updated, from the tree structure of the BIT (see the meaning of BIT[i] I gave above), you can immediate see that the parent node of [y], which has the index z=y+(y&-y) should be updated, and so is z+(z&-z), and so on and on, until the end of the BIT array.

• @rikimberley Thanks for sharing. This is a really brilliant way to solve this.

• hi, I think there's something wrong in your explanation part:
"*Example: given an array a[0]...a[7], we use a array BIT[9] to
*epresent a tree, where index [2] is the parent of [1] and [3], [6]
*is the parent of [5] and [7], [4] is the parent of [2] and [6], and
*[8] is the parent of [4]. I.e.,"

To correct:
index [2] is the parent of [1]
index [4] is the parent of [2] and [3]
index [8] is the parent of [4], [6] and [7]
index [6] is the parent of [5]

• @cuiyx9097 It looks like Binary Indexed Tree has two trees instead of one tree. For getSum operation, it has one tree; for update operation, it has another different tree. I learned this from here: http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

• @dachuan.huang Right. But I think the tree that the author mentioned at the beginning, is referring to the "update" tree. I think the "picture" is correctly drawn, while the above "example" is not.

• This explanation cannot be better...

• I found a very good explanation which expresses the intuition behind BIT here.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.