Binary Index Tree (Java) - ShuweiLeung/Thinking GitHub Wiki

1.（307:Medium）（非常经典题）Range Sum Query - Mutable

  • 该题需要一种特殊的数据结构才能在O(logn)的时间复杂度下完成update和query操作，这个数据结构就是Binary Indexed Tree或者Fenwick Tree。在进行update和query时，树的结构是不同的,通过控制加lowbit还是减lowbit来实现，如下图：

class NumArray {
    class FenwickTree {
	    int sums_[];
	    public FenwickTree(int n) {
	        sums_ = new int[n + 1]; //注意sums_数组的实际元素是索引1开始的
	    }
	    
	    public void update(int i, int delta) { //delta是相对于原来元素的更新值
	        while (i < sums_.length) {
	            sums_[i] += delta;
	            i += i & -i; //加上lowbit
	        }
	    }
	    
	    public int query(int i) { //求前n个数的和
	        int sum = 0;
	        while (i > 0) {
	            sum += sums_[i];
	            i -= i & -i; //减去lowbit
	        }
	        return sum;
	    }
	}
	
	FenwickTree tree;
	int[] nums;
	
	public NumArray(int[] nums) {
        tree = new FenwickTree(nums.length);
        this.nums = nums;
        for(int i = 0; i < nums.length; i++) {
        		tree.update(i+1, nums[i]);
        }
    }
    
    public void update(int i, int val) {
        tree.update(i+1, val-nums[i]);
        nums[i] = val;
    }
    
    public int sumRange(int i, int j) {
        return tree.query(j+1) - tree.query(i);
    }
}