Java Binary Indexed Tree


  • 15
    C

    Both update and getSum Complexity would be O(logn).

    Basic idea is we take the array as a tree when we initialize it where child node index equals to parent node index's last set bit - 1. When we get sum we take it as the tree where child node index equals to parent node index's last set bit + 1.

    Despite this, the general idea is similar to Range Sum Query I.

    For detail of Binary Indexed Tree you can take a look at this link http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

    public class NumArray {
    	int[] tree;
    	int[] nums;
    	int size;
        public NumArray(int[] nums) {
            this.size = nums.length;
            this.tree = new int[size + 1];
            this.nums = new int[size];
            this.nums = nums;
            for(int i = 0; i < size; i++){
            	updateTree(i, nums[i]);
            }
        }
    
        public void updateTree(int i, int val) {
            i = i + 1;
            while(i <= size){
            	tree[i] += val;
            	i += i & (-i); // the last set bit/ Two's complement
            }
        }
        
        public void update(int i, int val){
            updateTree(i, val - nums[i]);
            nums[i] = val;
        }
    
        private int getSum(int i){
        	int sum = 0;
        	i = i + 1;
        	while(i > 0){
        		sum += tree[i];
        		i -= i & (-i);// Another tree, go to the ancestor
        	}
        	return sum;
        }
    
        public int sumRange(int i, int j){
            if(i == 0) return getSum(j);
         	return getSum(j) - getSum(i - 1);
        }
    
      
    }

  • 0
    H

    Constructor takes o(n2) time?


  • 0
    Y

    @huangw3 it should be O(nlg(n)), for every element is lg(n)


Log in to reply
 

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