C++ Binary Indexed Tree implementation


  • 1
    L

    For Binary Indexed Tree, please see https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/ and vedio https://www.youtube.com/watch?v=CWDQJGaN1gY

    NumArray(vector<int> &nums) {
        tree = vector<int>(nums.size() + 1, 0);
        num = nums;
        for(int i = 0;i < num.size(); ++i)
            updateTree(i, num[i]);
    }
    void update(int idx, int val) {
         updateTree(idx, val - num[idx]);
         num[idx] = val;
    }
    
    int sumRange(int i, int j) {
         return read(j+1) - read(i);
    }
    
    int read(int idx)
    {
        int sum = 0;
        while (idx > 0){
            sum += tree[idx];
            idx -= (idx & -idx);
        }
        return sum;
    }
    void updateTree(int idx, int val) {
        idx = idx + 1;
        while(idx <= num.size()){
            tree[idx] += val;
            idx += idx & (-idx); // next node to update
        }
    }
    vector<int> tree; // tree array for Binary Indexed
    vector<int> num; // original array
    

Log in to reply
 

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