欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 307. Range Sum Query - Mutable

程序员文章站 2022-07-13 11:03:37
...

题目:

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
思路:

直接统计是不行的。继续思考,然后把数组分段,每10个为一小段,把每个小段的总数记录下来存在map里面,当更新时,更新map里面相应的小段的总数值,更新相应数组相应位置的值;统计的时候,如果区间小于10,遍历统计返回,区间大于10,在map里面统计以10为区间的相对应的总值,再加上前面不满一个区间和后面不满一个区间的值。结果还是GG,答案是用树状树状,感觉已经很接近了,大神们还是厉害。

树状数组:

leetcode 307. Range Sum Query - Mutable

C8 为a1到a8的和,把a1~a8分为a1~a4和a5~a8(二分法),a1~a4为C4,然后继续向下分,关键是下标开始从1开始,然后计算lowbit即可。

ck表示从ak开始往左连续求lowbit(k)个数的和

而lowbit我觉得代表的是前面半段的长度,

class NumArray {
    vector<int> tree;
	vector<int> re;
public:
    NumArray(vector<int> nums) {
        tree.resize(nums.size()+1,0);
		re = nums;
        for(int i = 0; i < nums.size(); i++) {
            int k = i+1;
            while(k<=nums.size())  
            {  
                tree[k]+=nums[i];  
                k+=k&-k;  
            }
        }
    }
    
    void update(int i, int val) {
        int k = i + 1;
        while(k<=re.size())  
        {  
            tree[k]+=val-re[i];  
            k+=k&-k;  
        } 
        re[i] = val; 
    }
    
    int sumRange(int i, int j) {
        int sum1 = 0, sum2 = 0;  
        int k = j + 1;
        while(i)  
        {  
            sum1+=tree[i];  
            i-=i&-i;  
        }  
        while(k)  
        {  
            sum2+=tree[k];  
            k-=k&-k;  
        } 
        return sum2 - sum1 ;
    }
};

PS:线段树

http://www.cnblogs.com/TenosDoIt/p/3453089.html

leetcode 307. Range Sum Query - Mutable

白色为叶子节点,单个区间,吧整个数组分成两半,分别求左右节点的最值(根据题目要求自己设定)

/*
功能:线段树的区间查询
root:当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
[qstart, qend]: 此次查询的区间
*/
int query(int root, int nstart, int nend, int qstart, int qend)
{
    //查询区间和当前节点区间没有交集
    if(qstart > nend || qend < nstart)
        return INFINITE;
    //当前节点区间包含在查询区间内
    if(qstart <= nstart && qend >= nend)
        return segTree[root].val;
    //分别从左右子树查询,返回两者查询结果的较小值
    int mid = (nstart + nend) / 2;
    return min(query(root*2+1, nstart, mid, qstart, qend),
               query(root*2+2, mid + 1, nend, qstart, qend));

}