C++ Solution using Binary Indexed Tree(B.I.T) which beats 97.87%


  • 0
    _
    //using Binary Indexed Tree(B.I.T)
    class NumArray {
    public:
        vector<int> c;
        int len;
        int lowBits(int x) {
            return x & (-x);
        }
        void update(int pos, int num) {
            while (pos <= len) {   
                c[pos] += num;   
                pos += lowBits(pos);   
            } 
        }
        int sum(int pos) {
            int res = 0;
            while (pos > 0) {
                res += c[pos];
                pos -= lowBits(pos);
            }
            return res;
        }
        NumArray(vector<int> nums) {
            len = nums.size();
            vector<int> tc(len + 1, 0);
            this->c = tc;
            
            for (int i = 0; i < len; i++) {
                update(i + 1, nums[i]);
            }
        }
        
        int sumRange(int i, int j) {
            return sum(j + 1) - sum(i);
        }
    };
    
    /**
     * Your NumArray object will be instantiated and called as such:
     * NumArray obj = new NumArray(nums);
     * int param_1 = obj.sumRange(i,j);
     */
    

Log in to reply
 

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