Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 307. Range Sum Query - Mutable

---

參考資訊：
https://www.cnblogs.com/grandyang/p/4985506.html

題目：


方法：

Fenwick Tree

解答：

class NumArray {
private:
    int n;
    vector<int> tree;
    vector<int> nums;

    int low_bit(int x) {
        return x & -x;
    }

    void add(int index, int delta) {
        for (int i = index; i <= n; i += low_bit(i)) {
            tree[i] += delta;
        }
    }

    int query(int index) {
        int sum = 0;

        for (int i = index; i > 0; i -= low_bit(i)) {
            sum += tree[i];
        }
        return sum;
    }

public:
    NumArray(vector<int>& nums) {
        this->nums = nums;
        n = nums.size();
        tree.resize(n + 1, 0);

        for (int i = 0; i < n; ++i) {
            add(i + 1, nums[i]);
        }
    }
    
    void update(int index, int val) {
        int delta = val - nums[index];
        nums[index] = val;
        add(index + 1, delta);
    }
    
    int sumRange(int left, int right) {
        return query(right + 1) - query(left);
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(index,val);
 * int param_2 = obj->sumRange(left,right);
 */