leetcode 307. Range Sum Query - Mutable

比眉伴天荒 2022-07-26 12:15 152阅读 0赞

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The  update(i, val)  function modifies  nums  by updating the element at index  i  to  val .

Example:

Given nums = [1, 3, 5]
    
    sumRange(0, 2) -> 9
    update(1, 2)
    sumRange(0, 2) -> 8

Note:

1.  The array is only modifiable by the update function.
2.  You may assume the number of calls to update and sumRange function is distributed evenly.

这题貌似简单，但你用naive的解法去解绝壁要超时。明眼人一眼就看出来了，这题要用树状数组来解决。如果你以前从没听说过什么线段树、树状数组，完全是自己想出来的，那你就是个天才。

树状数组在这里就不讲解了，自己搜去。

class NumArray {
    private:
        vector<int> c;
        vector<int> m_nums;
    public:
        NumArray(vector<int> &nums) {
            c.resize(nums.size() + 1);
            m_nums = nums;
            for (int i = 0; i < nums.size(); i++){
                add(i + 1, nums[i]);
            }
        }
    
        int lowbit(int pos){
            return pos&(-pos);
        }
    
        void add(int pos, int value){
            while (pos < c.size()){
                c[pos] += value;
                pos += lowbit(pos);
            }
        }
        int sum(int pos){
            int res = 0;
            while (pos > 0){
                res += c[pos];
                pos -= lowbit(pos);
            }
            return res;
        }
    
        void update(int i, int val) {
            int ori = m_nums[i];
            int delta = val - ori;
            m_nums[i] = val;
            add(i + 1, delta);
        }
    
        int sumRange(int i, int j) {
            return sum(j + 1) - sum(i);
        }
    };