leetcodeノート:Range Sum Query-Mutable

一.タイトルの説明
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: The array is only modifiable by the update function. You may assume the number of calls to update and sumRange function is distributed evenly.
二.テーマ分析
問題はRange Sum Query-Immutableの問題に基づいて増加する難易度であり,配列numsを入力すると配列の要素を修正でき,毎回1つの要素しか修正できないことが要求される.同様に配列のある区間和を求める機能を実現する.
次の場合http://blog.csdn.net/liyuefeilong/article/details/505516621つの問題のやり方を少し改善すると、機能を実現できますが、タイムアウトします.
この時、いくつかの文章を読んでから、元の古典的なやり方(前の問題を含む)は木状の配列を使ってこの配列numsを維持することであり、その挿入とクエリーはO(logn)の複雑さを実現することができ、非常に巧みであることが分かった.
ツリー配列については、以下のブログでよく説明しています.
http://blog.csdn.net/int64ago/article/details/7429868
三.サンプルコード

//   
class NumArray {
public:
    NumArray(vector<int> &nums) {
        if (nums.empty()) return;
        else
        {
            sums.push_back(nums[0]);
            //        
            int len = nums.size();
            for (int i = 1; i < len; ++i)
                sums.push_back(sums[i - 1] + nums[i]);
        }
    }

    void update(int i, int val) {
        for (int k = i; k < nums.size(); ++k)
            sums[k] += (val - nums[i]);
        nums[i] = val;
    }

    int sumRange(int i, int j) {
        return sums[j] - sums[i - 1];
    }

private:
    vector<int> nums;
    //     
    vector<int> sums;
};


// 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);

//            AC，    O(logn)
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);
    }
};
// 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);

四.小結
前に聞いたことがあるだけで、これは初めて木の配列を使って、これは配列を維持する1つのとても良い思想で、深く学ぶ必要があります!