# Solutions using Binary Indexed tree and Segment tree

• Binary indexed tree version

public class NumArray {
int[] bit;
public NumArray(int[] nums) {
bit = new int[nums.length+1];
for(int i=0;i<nums.length;i++)
{
int index=i+1;
while(index<=nums.length)
{
bit[index]+=nums[i];
index+=index&(-index);
}
}
}

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

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

segment tree version

public class NumArray {
int [] st;
int len ;
public NumArray(int[] nums) {

// tree height log_2 n
len=nums.length;
if(len<=0) return;
int h = (int)Math.ceil(Math.log(len)/Math.log(2));
//max num of nodex;
// 2^(h+1)-1;
int max_size = (int)Math.pow(2,h+1)-1;

st= new int[max_size];
constructSTUtil(nums,0,len-1,0);
}

private int constructSTUtil(int[] nums, int l , int r, int i)
{
if(l==r)
{
st[i]=nums[l];
return st[i];
}
int mid=(l+r)/2;
st[i]=constructSTUtil(nums,l,mid,2*i+1)+constructSTUtil(nums,mid+1,r,2*i+2);
return st[i];
}

public int sumRange(int i, int j) {
return sumRangeUtil(0,len-1,i,j,0);
}

private int sumRangeUtil(int l, int r, int ql, int qr, int i)
{
if(ql<=l && qr>=r) return st[i];
if(ql>r || qr<l) return 0;
int mid=(l+r)/2;
return sumRangeUtil(l,mid,ql,qr,i*2+1)+sumRangeUtil(mid+1,r,ql,qr,i*2+2) ;
}
}

/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/

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