Java using Binary Indexed Tree with clear explanation


  • 126
    R

    This is to share the explanation of the BIT and the meaning of the bit operations.

    public class NumArray {
    	/**
    	 * Binary Indexed Trees (BIT or Fenwick tree):
    	 * https://www.topcoder.com/community/data-science/data-science-
    	 * tutorials/binary-indexed-trees/
    	 * 
    	 * Example: given an array a[0]...a[7], we use a array BIT[9] to
    	 * represent a tree, where index [2] is the parent of [1] and [3], [6]
    	 * is the parent of [5] and [7], [4] is the parent of [2] and [6], and
    	 * [8] is the parent of [4]. I.e.,
    	 * 
    	 * BIT[] as a binary tree:
    	 *            ______________*
    	 *            ______*
    	 *            __*     __*
    	 *            *   *   *   *
    	 * indices: 0 1 2 3 4 5 6 7 8
    	 * 
    	 * BIT[i] = ([i] is a left child) ? the partial sum from its left most
    	 * descendant to itself : the partial sum from its parent (exclusive) to
    	 * itself. (check the range of "__").
    	 * 
    	 * Eg. BIT[1]=a[0], BIT[2]=a[1]+BIT[1]=a[1]+a[0], BIT[3]=a[2],
    	 * BIT[4]=a[3]+BIT[3]+BIT[2]=a[3]+a[2]+a[1]+a[0],
    	 * BIT[6]=a[5]+BIT[5]=a[5]+a[4],
    	 * BIT[8]=a[7]+BIT[7]+BIT[6]+BIT[4]=a[7]+a[6]+...+a[0], ...
    	 * 
    	 * Thus, to update a[1]=BIT[2], we shall update BIT[2], BIT[4], BIT[8],
    	 * i.e., for current [i], the next update [j] is j=i+(i&-i) //double the
    	 * last 1-bit from [i].
    	 * 
    	 * Similarly, to get the partial sum up to a[6]=BIT[7], we shall get the
    	 * sum of BIT[7], BIT[6], BIT[4], i.e., for current [i], the next
    	 * summand [j] is j=i-(i&-i) // delete the last 1-bit from [i].
    	 * 
    	 * To obtain the original value of a[7] (corresponding to index [8] of
    	 * BIT), we have to subtract BIT[7], BIT[6], BIT[4] from BIT[8], i.e.,
    	 * starting from [idx-1], for current [i], the next subtrahend [j] is
    	 * j=i-(i&-i), up to j==idx-(idx&-idx) exclusive. (However, a quicker
    	 * way but using extra space is to store the original array.)
    	 */
    
    	int[] nums;
    	int[] BIT;
    	int n;
    
    	public NumArray(int[] nums) {
    		this.nums = nums;
    
    		n = nums.length;
    		BIT = new int[n + 1];
    		for (int i = 0; i < n; i++)
    			init(i, nums[i]);
    	}
    
    	public void init(int i, int val) {
    		i++;
    		while (i <= n) {
    			BIT[i] += val;
    			i += (i & -i);
    		}
    	}
    
    	void update(int i, int val) {
    		int diff = val - nums[i];
    		nums[i] = val;
    		init(i, diff);
    	}
    
    	public int getSum(int i) {
    		int sum = 0;
    		i++;
    		while (i > 0) {
    			sum += BIT[i];
    			i -= (i & -i);
    		}
    		return sum;
    	}
    
    	public int sumRange(int i, int j) {
    		return getSum(j) - getSum(i - 1);
    	}
    }
    
    // Your NumArray object will be instantiated and called as such:
    // NumArray numArray = new NumArray(nums);
    // numArray.sumRange(0, 1);
    // numArray.update(1, 10);
    // numArray.sumRange(1, 2);

  • 0
    C

    The explanation is so clear, thanks for your sharing, it is a brilliant method.


  • 0
    G

    Best explanation so far, thank you so much


  • 1

    Similiar C++ implementation based others' posts.

    I have refered to the post from GeekForGeek

    http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

    I think the key points are that you should set "i++" and understand the relationship of the children and parents.

     class NumArray {
        private:
            vector<int> _nums;
            vector<int> bit;
            
            int lower_bit(int i){
                return i&-i;
            }
            
            int query(int i){
                i++;
                int sum=0;
                while(i>0){
                    sum+=bit[i];
                    i-=lower_bit(i);
                }
                return sum;
            }
            
            void add(int i, int val){
                i++;
                while(i<bit.size()){
                    bit[i]+=val;
                    i+=lower_bit(i);
                }
            }
            
        public:
            NumArray(vector<int> &nums) : _nums(nums) {
                bit.resize(nums.size()+1);
                for(int i=0; i<nums.size(); i++){
                    add(i, nums[i]);
                }
            }
        
            void update(int i, int val) {
                if(val!=_nums[i]){
                    add(i, val-_nums[i]);
                    _nums[i]=val;
                }
            }
        
            int sumRange(int i, int j) {
                return query(j)-query(i-1);
            }
        };
    

  • 2
    D

    @rikimberley Do you have any idea that why we need to do y += y & (-y) to update?

    Here is my understanding so far.

    I know x & (-x) gets the LSB (least significant bit).

    I know that index x manages the sum in the range [x - x & (-x), x - 1].

    So whenever index y gets update, we need to update all indices x such that x - x & (-x) <= y <= x - 1. However, I don't know how to solve this in-equation. I know the answer is: y + y & (-y), and continue. But why?


  • 2
    R

    @dachuan.huang said in Java using Binary Indexed Tree with clear explanation:

    range

    Hi,

    Solving the inequality the you gave is not easy, but you can view in a different angle. That is, once an index (of BIT array) [y] is updated, from the tree structure of the BIT (see the meaning of BIT[i] I gave above), you can immediate see that the parent node of [y], which has the index z=y+(y&-y) should be updated, and so is z+(z&-z), and so on and on, until the end of the BIT array.


  • 0
    G

    @rikimberley Thanks for sharing. This is a really brilliant way to solve this.


  • 0
    C

    hi, I think there's something wrong in your explanation part:
    "*Example: given an array a[0]...a[7], we use a array BIT[9] to
    *epresent a tree, where index [2] is the parent of [1] and [3], [6]
    *is the parent of [5] and [7], [4] is the parent of [2] and [6], and
    *[8] is the parent of [4]. I.e.,"

    To correct:
    index [2] is the parent of [1]
    index [4] is the parent of [2] and [3]
    index [8] is the parent of [4], [6] and [7]
    index [6] is the parent of [5]


  • 0
    D

    @cuiyx9097 It looks like Binary Indexed Tree has two trees instead of one tree. For getSum operation, it has one tree; for update operation, it has another different tree. I learned this from here: http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/


  • 0
    C

    @dachuan.huang Right. But I think the tree that the author mentioned at the beginning, is referring to the "update" tree. I think the "picture" is correctly drawn, while the above "example" is not.


  • 0
    O

    This explanation cannot be better...


  • 6
    X

    I found a very good explanation which expresses the intuition behind BIT here.


Log in to reply
 

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