# My new Java AC solution with heap, beat 50%, but potentially can be further optimized.

• The idea is to construct a heap with parent is the sum of two leaves, the root is bt[1] which hold the sum of the whole array. Use bt[1] as root. not bt[0], so we can calculate the parent index by

``````parent_index = leaf_index >> 1
``````

to easily get the sum of all children.

In this way, update a node only effect the path node from the leave to root, therefore it is O(logn)

getting sum is little bit more tricky, it uses

``````sum(i, j) = sum(0, j) - sum(0, i) + num[i];
``````

Here is the code.

``````public class NumArray {
int[] bt;
int twoAlign;

private int getLog2(int i) {
int c = 0;
while(i > (1 << c)) {
c++;
}
return c;
}

public NumArray(int[] nums) {
int len = nums.length;
twoAlign = getLog2(len);
bt = new int[1<<(twoAlign+1)];
for (int i = 0; i < nums.length; i++) {
bt[i+(1<<twoAlign)] = nums[i];
}
int c= twoAlign;
while(c > 0) {
c--;
for (int i = 0; i < (1 << c); i++) {
bt[i+(1<<c)] = bt[2*(i+(1<<c))] +  bt[2*(i+(1<<c))+1];
}
}
}

void update(int i, int val) {
int iChild = i+(1<<twoAlign);
bt[iChild] = val;
while((iChild >> 1) > 0) {
iChild >>= 1;
bt[iChild] = bt[iChild << 1] + bt[(iChild <<1)+1];
}
}

private int sum0(int i) {
int sum0 = 0;
int c = 0;
i++;
while(i > 0) {
if ((i & (1 << c)) != 0) {
sum0 += bt[((1<<twoAlign) + i-1) >> c];
i -= (1 << c);
}
c++;
}
return sum0;
}

public int sumRange(int i, int j) {
return sum0(j) - sum0(i) + bt[i + (1<<twoAlign)];
}
}
``````

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