leetcode 307. 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.

题解：树状数组最基本的用法（点更新，区间查询）。需要注意的是这里的点更新不是把点加一个值，而是完全更新一个点的值，这就需要不仅仅更新树状数组，原数组的值也应该更新，因为可能下一个还会更新这个点，那么就需要知道它之前的值是多少。

class NumArray {

public:

    NumArray(vector<int> &nums) {

        n = nums.size();

        c=vector<int>(n+,);

        a=vector<int>(n+,);

        for(int i=;i<=n;i++){

            update(i-,nums[i-]);

        }

    }

    int lowbit(int x){

        return x&-x;

    }

    void update(int i, int val) {

        int old = a[i+];

        for(int k=i+;k<=n;k+=lowbit(k)){

            c[k]-=old;

            c[k]+=val;

        }

        a[i+]=val;

    }

    int sum(int x){

        int s=;

        while(x>){

            s+=c[x];

            x-=lowbit(x);

        }

        return s;

    }

    int sumRange(int i, int j) {

        return sum(j+)-sum(i);

    }

private:

    int n;

    vector<int>c;

    vector<int>a;

};

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

巴特西

leetcode 307. Range Sum Query - Mutable(树状数组)

最新文章

热门文章