Concise Version BIT


  • 0
    L

    class NumArray {
    public:
    NumArray(vector<int> nums) : n(nums.size()), nums(n), BIT(n+1) {
    for (int i = 0; i < n; ++i) update(i, nums[i]);
    }
    void update(int i, int val) {
    int diff = val - nums[i];
    nums[i] = val;
    for(int j=i+1; j<=n; j+=(j&-j)) BIT[j] += diff;
    }
    int sumRange(int i, int j) {
    return getSum(j) - getSum(i - 1);
    }
    private:
    int n;
    vector<int> nums, BIT;
    int getSum(int i) {
    int sum = 0;
    for(int j=i+1; j>0; j-=(j&-j)) sum += BIT[j];
    return sum;
    }
    };


Log in to reply
 

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