# Java solution using simple Augmented Data Structure beats 95% solutions

• Creating a tree and storing sum of left nodes and right nodes on the root. For calculating getSum, first get sum from 0-j and then subtract sum from i-1which gives us the answer.

public class NumArray {

``````Tree root;
int size;

Tree createTree(int[] nums, int s, int e)
{
if(s>e) return null;

int mid = (s+e)/2;

Tree left = createTree(nums,s,mid-1);
Tree right = createTree(nums,mid+1,e);

return new Tree(mid,nums[mid],left,right);
}

int updateTree(Tree node,int index, int val)
{
if(node == null) return 0;
if(node.index ==index)
{
int diff = val-node.val;
node.val = val;
return diff;
}
int diff =0;
if(node.index>index)
{
diff = updateTree(node.left,index,val);
node.leftsum += diff;
}
else
{
diff = updateTree(node.right,index,val);
node.rightsum += diff;
}
return diff;
}

int getSum(Tree node, int index, boolean isDiff)
{
if(node==null) return 0;

if(node.index==index)
{
return node.leftsum+node.val;
}
else if(node.index>index)
{
return getSum(node.left,index,isDiff);
}
else
{
return node.leftsum+node.val+getSum(node.right,index,isDiff);
}
}

public NumArray(int[] nums) {
if(nums==null || nums.length==0) return;
root = createTree(nums,0,nums.length-1);
size = nums.length-1;
}

public void update(int i, int val) {
if(i>=0 && i<=size)
updateTree(root,i,val);
}

public int sumRange(int i, int j) {
int sum = getSum(root,j,false);
return i>0?sum-getSum(root,i-1,true):sum;
}
``````

}

class Tree
{
int index;
int val;
int leftsum;
int rightsum;
Tree left;
Tree right;
Tree(int i, int v, Tree l, Tree r)
{
index = i;
val = v;
left = l;
right = r;
if(left!=null) leftsum = left.leftsum+left.rightsum+left.val;
if(right!=null) rightsum = right.leftsum+right.rightsum+right.val;
}
}

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