c++ 48ms, binary indexed tree solution.


  • 0

    For more information about BIT, please check https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/

    class NumArray {
    
    private:
    vector<int> bit,data;
    
    public:
    NumArray(vector<int> &nums) {
        data = nums;
        if (nums.empty()) return;
        int sz=nums.size();
        bit = vector<int>(sz+1,0);
        for (int i=1;i<=sz;i++){
            int k=i;
            while(k<=sz){
                bit[k]+=nums[i-1];
                k = k+(k&(~(k-1)));
            }
        }
    }
    
    void update(int i, int val) {
        int diff = val-data[i];
        data[i]=val;
        int k=i+1;
        while(k<=data.size()){
            bit[k]+=diff;
            k = k+(k&(~(k-1)));
        }
    }
    
    int sumRange(int i, int j) {
        if (i==0) return sumSub(j);
        else return sumSub(j)-sumSub(i-1);
    }
    
    int sumSub(int i){
        int k=i+1,res=0;
        while(k){
            res+=bit[k];
            k=k&(k-1);
        }
        return res;
    }
    };

Log in to reply
 

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