C++ binary indexed tree solution


  • 0
    I
    class NumArray {
    public:
        NumArray(vector<int> &nums) {
            BIT.resize(nums.size() + 1, 0);
            for (int i = 0; i < nums.size(); i++) BIT[i + 1] = nums[i];
            int gap = 2;
            while (gap < BIT.size()) {
                for (int i = gap; i < BIT.size(); i += gap) BIT[i] += BIT[i - gap / 2];
                gap *= 2;
            }
        }
    
        void update(int i, int val) {
            int diff = val - sumRange(i, i);
            for ( i++; i < BIT.size(); i += (i & -i)) {
                BIT[i] += diff;
            }
        }
    
        int getSum(int i) {
            int ret = 0;
            while (i) {
                ret += BIT[i];
                i &= (i - 1);
            }
            return ret;
        }
    
        int sumRange(int i, int j) {
            return getSum(j + 1) - getSum(i);
        }
    private:
        vector<int> BIT;
    };

Log in to reply
 

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