leetcode 307. Range Sum Query - Mutable 树状数组的一个应用

「爱情、让人受尽委屈。」 2022-06-06 23:39 118阅读 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:  
The array is only modifiable by the update function.  
You may assume the number of calls to update and sumRange function is distributed evenly.

**题意很简单，但是我的做法总是超时，想了好久没想到更好的方法，网上看了个答案，原来还可以这么做。树状数组没学过，也不知道又该怎么做，所以这道题就先记着吧。**

要和这道题[leetcode 304. Range Sum Query 2D - Immutable 子矩阵求和 + DP][leetcode 304. Range Sum Query 2D - Immutable _ _ DP] 和 这道题[leetcode 303. Range Sum Query - Immutable 字串求和 + DP][leetcode 303. Range Sum Query - Immutable _ _ DP] 一起学习。

建议和[leetcode 327. Count of Range Sum 字段和问题 + 动态规划DP解决 + 字段数 + 暴力求解真好][leetcode 327. Count of Range Sum _ _ _DP_ _ _ _] 一起学习

代码如下：

import java.util.Arrays;
    
    
    
    /*
     *使用树状数组这一个数据结构，自行掌握吧，
     *http://www.cnblogs.com/xudong-bupt/p/3484080.html
     *或者使用线段树
     *
     *还是先记着吧，第一次接触
     *
     * */
    public class NumArray {
        /**
         * 使用
         * Binary Indexed Trees (BIT or Fenwick tree):
         * https://www.topcoder.com/community/data-science/data-science-
         * tutorials/binary-indexed-trees/
         * 
         * Example: given an array a[0]...a[7], we use a array BIT[9] to
         * represent a tree, where index [2] is the parent of [1] and [3], [6]
         * is the parent of [5] and [7], [4] is the parent of [2] and [6], and
         * [8] is the parent of [4]. I.e.,
         * 
         * BIT[] as a binary tree:
         *            ______________*
         *            ______*
         *            __*     __*
         *            *   *   *   *
         * indices: 0 1 2 3 4 5 6 7 8
         * 
         * BIT[i] = ([i] is a left child) ? the partial sum from its left most
         * descendant to itself : the partial sum from its parent (exclusive) to
         * itself. (check the range of "__").
         * 
         * Eg. BIT[1]=a[0], BIT[2]=a[1]+BIT[1]=a[1]+a[0], BIT[3]=a[2],
         * BIT[4]=a[3]+BIT[3]+BIT[2]=a[3]+a[2]+a[1]+a[0],
         * BIT[6]=a[5]+BIT[5]=a[5]+a[4],
         * BIT[8]=a[7]+BIT[7]+BIT[6]+BIT[4]=a[7]+a[6]+...+a[0], ...
         * 
         * Thus, to update a[1]=BIT[2], we shall update BIT[2], BIT[4], BIT[8],
         * i.e., for current [i], the next update [j] is j=i+(i&-i) //double the
         * last 1-bit from [i].
         * 
         * Similarly, to get the partial sum up to a[6]=BIT[7], we shall get the
         * sum of BIT[7], BIT[6], BIT[4], i.e., for current [i], the next
         * summand [j] is j=i-(i&-i) // delete the last 1-bit from [i].
         * 
         * To obtain the original value of a[7] (corresponding to index [8] of
         * BIT), we have to subtract BIT[7], BIT[6], BIT[4] from BIT[8], i.e.,
         * starting from [idx-1], for current [i], the next subtrahend [j] is
         * j=i-(i&-i), up to j==idx-(idx&-idx) exclusive. (However, a quicker
         * way but using extra space is to store the original array.)
         */
    
        int[] nums=null;
        int[] BIT=null;
    
        public NumArray(int[] nums) 
        {
            this.nums=new int[nums.length];
            BIT=new int[nums.length+1];
            Arrays.fill(BIT, 0);
    
            for(int i=0;i<nums.length;i++)
            {
                this.nums[i]=nums[i];
                init(i, nums[i]);
            }
    
        }
    
        public int lowBit(int i) 
        {
            return i&(-i);
        }
        public void init(int i, int val) 
        {
            i=i+1;
            while(i<=nums.length)
            {
                BIT[i]+=val;
                i+=lowBit(i);
            }
        }
    
        void update(int i, int val)
        {
            int diff=val-nums[i];
            nums[i]=val;
            init(i, diff);
        }
    
        public int getSum(int i) 
        {
            i=i+1;
            int sum=0;
            while(i>0)
            {
                sum+=BIT[i];
                i-=lowBit(i);
            }
            return sum;
        }
    
        public int sumRange(int i, int j) 
        {
            return getSum(j)-getSum(i-1);
        }
    }
    
    // Your NumArray object will be instantiated and called as such:
    // NumArray numArray = new NumArray(nums);
    // numArray.sumRange(0, 1);
    // numArray.update(1, 10);
    // numArray.sumRange(1, 2);
    
    
    /*public class NumArray
    {
        public static int[] num=null;
        public static int[] sum=null;
        public NumArray(int[] nums)
        {
            if(nums==null || nums.length<=0)
                return ;
    
            num=new int[nums.length];
            sum=new int[nums.length];
            sum[0]=nums[0];
            num[0]=nums[0];
            for(int i=1;i<nums.length;i++)
            {
                 sum[i]=sum[i-1]+nums[i];
                 num[i]=nums[i];
            }
        }
    
        public void update(int i, int val) 
        {
            if(i<0 || i>=num.length)
                return ;
            num[i]=val;
            if(i==0)
            {
                 sum[0]=val;
                 for(int j=1;j<num.length;j++)
                    sum[j]=sum[j-1]+num[j];
            }else 
            {
                for(int j=i;j<num.length;j++)
                    sum[j]=sum[j-1]+num[j];
            }
        }
    
        public int sumRange(int i, int j)
        {
            if(sum==null || sum.length<=0 || i<0 || i>=num.length || j<0 || j>=num.length)
                return -1;
            if(i==0)
                return sum[j];
            else 
                return sum[j]-sum[i-1];
        }
    }
    */

下面是C++的代码，先这么做吧

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class NumArray 
    {
    public:
        vector<int> sums;
        vector<int> nums;
    
        NumArray(vector<int> a)
        {
            nums = a;
            sums.resize(nums.size() + 1);
            for (int i = 0; i<nums.size(); i++)
            {
                change(i + 1, nums[i]);
            }
        }
    
        void change(int i, int vals) 
        {
            while (i<sums.size()) 
            {
                sums[i] += vals;
                i += lowbit(i);
            }
        }
    
        int lowbit(int x)
        {
            return x&(-x);
        }
    
        int sum(int n) 
        {
            int sum = 0;
            while (n>0) 
            {
                sum += sums[n];
                n -= lowbit(n);
            }
            return sum;
        }
    
    
        void update(int i, int val) 
        {
            int delta = val - nums[i];
            nums[i] = val;
            change(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 obj = new NumArray(nums);
    * obj.update(i,val);
    * int param_2 = obj.sumRange(i,j);
    */

[leetcode 304. Range Sum Query 2D - Immutable _ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/78131464
[leetcode 303. Range Sum Query - Immutable _ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/78131390
[leetcode 327. Count of Range Sum _ _ _DP_ _ _ _]: http://blog.csdn.net/jackzhang_123/article/details/78150616