Another easy to understand Fenwick Tree implementation. Beats 97%


  • 0
    Z
    class NumArray {
        int[] biTree;
        int[] nums;
        public NumArray(int[] nums) {
            this.biTree = createTree(nums);
            this.nums = nums;
        }
    
        public void update(int i, int val) {
            if(biTree.length == 1){
                return;
            }
            updateTree(biTree, val - nums[i], i+1);
            nums[i] = val;
        }
    
        public int sumRange(int i, int j) {
            if(biTree.length == 1){
                return 0;
            }
            return getSum(biTree, j) - getSum(biTree, i-1);
        }
    
    
    
        public int getNext(int index){
            return index + (index & -index);
        }
    
        public int getSum(int binaryIndexedTree[], int index){
            index = index + 1;
            int sum = 0;
            while(index > 0){
                sum += binaryIndexedTree[index];
                index = getParent(index);
            }
            return sum;
        }
    
        public int getParent(int index){
            return index - (index & -index);
        }
    
        public void updateTree(int[] biTree, int val, int pos){
            while(pos < biTree.length){
                biTree[pos] += val;
                pos = getNext(pos);
            }
        }
    
        public int[] createTree(int[] nums){
            int[] biTree = new int[nums.length+1];
            for(int i = 0; i<nums.length; i++){
                updateTree(biTree, nums[i], i+1);
            }
            return biTree;
        }
        
    }
    
    

Log in to reply
 

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