JAVA Binary Indexed Tree


  • 0
    Y
    public class NumArray {
    
        int[] tree;
        int[] nums;
        int len;
        public NumArray(int[] nums) {
            this.nums = nums;
            len = nums.length;
            tree = new int[len + 1];
            for(int i = 0; i < len; i++) {
                buildTree(i);
            }
            // for(int num: nums)
            //     System.out.print(num + "  ");
            // System.out.println();
            // for(int num: tree)
            //     System.out.print(num + "  ");
        }
        
        public void buildTree(int i) {
            int idx = i + 1;
            while(idx <= len) {
                tree[idx] += nums[i];
                idx += (-idx) & idx;
            }
        }
        
        public int getSum(int i) {
            int sum = 0;
            i++;
            while(i > 0) {
                sum += tree[i];
                i -= (-i) & i;
            }
            
            return sum;
        }
    
        public int sumRange(int i, int j) {
            if(i <= len && j < len)
                return getSum(j) - getSum(i - 1);
            return 0;
        }
    }
    
    
    // Your NumArray object will be instantiated and called as such:
    // NumArray numArray = new NumArray(nums);
    // numArray.sumRange(0, 1);
    // numArray.sumRange(1, 2);

Log in to reply
 

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