Java solution using simple Augmented Data Structure beats 95% solutions


  • 0
    A

    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;
    }
    }


Log in to reply
 

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