# Typical solution using Binary Indexed Tree

• public class NumArray {

``````int[]tree;
int[]prev;

public NumArray(int[] nums) {
if(nums==null||nums.length==0) return;
int len=nums.length;
tree = new int[len+1];
prev = new int[len];
for(int i=0;i<len;i++){
update(i,nums[i]);
}
}

void update(int i, int val) {
int delta=val-prev[i];
for(int index=i+1;index<tree.length;index+=index&(-index)){
tree[index]+=delta;
}
prev[i]=val;
}

public int sum(int i){
int res=0;
for(int index=i+1;index>0;index-=index&(-index)){
res+=tree[index];
}
return res;
}

public int sumRange(int i, int j) {
if(i==0) return sum(j);
else{
return sum(j)-sum(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);

• Actually this problem can be solved by using segment tree. In another word, segment tree is more powerful than BIT. However, it`s relatively easy to solve the problem if BIT solution is feasible.

• Segment Tree Solution:

public class NumArray {

``````//start to code the segment tree
class Node{
int start;
int end;
int sum;
Node left;
Node right;
public Node(int start, int end, int sum){
this.start=start;
this.end=end;
this.sum=sum;
left=null;
right=null;
}
}

public Node buildTree(int start, int end){
if(start>end) return null;
if(start==end) return new Node(start,end,0);
int mid=(start+end)/2;
Node root = new Node(start,end,0);
root.left=buildTree(start,mid);
root.right=buildTree(mid+1,end);
return root;
}

public void updateTree(Node root, int pos, int val){
if(root==null||pos>root.end||pos<root.start) return;
if(root.start==pos&&root.end==pos){
root.sum=val;
return;
}

int mid=(root.start+root.end)/2;
if(pos<=mid){
updateTree(root.left,pos,val);
}
else if(pos>mid){
updateTree(root.right,pos,val);
}

root.sum=root.left.sum+root.right.sum;
}

//[0,pos]
public int sum(Node root, int start, int end){
if(root==null||start>end) return 0;
if(root.start==start&&root.end==end) return root.sum;

int mid=(root.start+root.end)/2;
int left=0, right=0;
if(end<=mid){
left=sum(root.left,start,end);
}
else if(start>mid){
right=sum(root.right,start,end);
}
else{
left=sum(root.left,start,mid);
right=sum(root.right,mid+1,end);
}
return left+right;
}

//finish coding the segment tree
Node root;

public NumArray(int[] nums) {
if(nums==null||nums.length==0) return;
root=buildTree(0,nums.length-1);
for(int i=0;i<nums.length;i++){
updateTree(root,i,nums[i]);
}
}

void update(int i, int val) {
updateTree(root,i,val);
}

public int sumRange(int i, int j) {
return sum(root,i,j);
}
``````

}

// 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);

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