C++_Binary Index Tree (Recommended Video)


  • 1
    class NumArray {
    private:
    vector<int> _nums;//to store the input int vector: nums
    vector<int> bit;//Binary Index Tree! To store the subarray sum of nums
    
    int lower_bit(int i){
        return i&(-i);// To get the lowest 1 in this integer, this will be used for find the parent node and child node
    }
    
    int query(int i){//This function will be used to return the sum of 0 to i in nums (also _nums)
        i++;//because in BIT, we calculate the index from 1, so add 1 to i.
        int sum = 0;
        while(i > 0){
            sum +=  bit[i];
            i = i - lower_bit(i);//flip the lowest 1 to go back to the parent node till the root.
        }
        return sum;
    }
    
    void add(int i, int val){//add value "val" in the bit vector.
        i++;
        while(i < bit.size()){
            bit[i] += val;
            i += lower_bit(i);//We should also update all of the child nodes of this parent node
        }
    }
    
    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);
    
    }
    };

Log in to reply
 

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