Typical solution using Binary Indexed Tree


  • 0
    X

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


  • 0
    X

    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.


  • 0
    X

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


Log in to reply
 

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