Binary Indexed Tree Java Solution


  • 0
    M
        public class NumArray {		
    	private int[] bit, nums;
    	public NumArray(int[] nums) {
    		this.nums = nums;
    		int n = nums.length;
    		bit = new int[n + 1];
    		for (int i = 1; i <= n; ++i) {
    			increase(i, nums[i - 1]);
    		}
    	}
    	
    	public void update(int i, int val) {
    		increase(i + 1, val - nums[i]);
    		nums[i] = val;
    	}
    	
    	public int sumRange(int i, int j) {
    		return get(j + 1) - get(i);
    	}
    	
    	private void increase(int i, int d) {
    		while (i < bit.length) {
    			bit[i] += d;
    			i += (i & -i);
    		}
    	}
    	private int get(int i) {
    		int sum = 0;
    		while (i > 0) {
    			sum += bit[i];
    			i -= (i & -i);
    		}
    		return sum;
    	}
        }
    

Log in to reply
 

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