# Java Binary Indexed Tree

• Both update and getSum Complexity would be O(logn).

Basic idea is we take the array as a tree when we initialize it where child node index equals to parent node index's last set bit - 1. When we get sum we take it as the tree where child node index equals to parent node index's last set bit + 1.

Despite this, the general idea is similar to Range Sum Query I.

For detail of Binary Indexed Tree you can take a look at this link http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

``````public class NumArray {
int[] tree;
int[] nums;
int size;
public NumArray(int[] nums) {
this.size = nums.length;
this.tree = new int[size + 1];
this.nums = new int[size];
this.nums = nums;
for(int i = 0; i < size; i++){
updateTree(i, nums[i]);
}
}

public void updateTree(int i, int val) {
i = i + 1;
while(i <= size){
tree[i] += val;
i += i & (-i); // the last set bit/ Two's complement
}
}

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

private int getSum(int i){
int sum = 0;
i = i + 1;
while(i > 0){
sum += tree[i];
i -= i & (-i);// Another tree, go to the ancestor
}
return sum;
}

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

}``````

• Constructor takes o(n2) time?

• @huangw3 it should be O(nlg(n)), for every element is lg(n)

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