307. Range Sum Query Mutable - cocoder39/coco39_LC GitHub Wiki

307. Range Sum Query - Mutable

O(n * log n) for pre-process, O(log n) for add(), O(log n) for query()

class NumArray {
public:
    NumArray(vector<int> &nums) : copy(nums) {
        bit.resize(nums.size() + 1);
        for (int i = 0; i < nums.size(); i++)
            add(i, nums[i]);
    }

    void update(int i, int val) {
        int inc = val - copy[i];
        if (inc == 0)   return;
        copy[i] = val;
        add(i, inc);
    }

    int sumRange(int i, int j) {
        return query(j) - query(i - 1);
    }
private:
    vector<int> copy;
    vector<int> bit; //sum of a range
    
    void add(int i, int val) {
        int idx = i + 1;
        for (; idx < bit.size(); idx += (idx & -idx))
            bit[idx] += val;
    }
    
    int query(int i) {
        int sum = 0;
        int idx = i + 1;
        for (; idx > 0; idx -= (idx & -idx))
            sum += bit[idx];
        return sum;
    }
};


// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);
⚠️ **GitHub.com Fallback** ⚠️