[LeetCode]Range Sum Query

题目链接: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.

题目解法:

题目要求快速的处理数组的部分和，因此很容易联想到树状数组，树状数组是一种用于通过辅助数组和位置算法实现动态管理部分和的一种算法，其核心函数为lowbit、add、sum，当我们需要加入一个元素时，使用add函数向某个位置注入值，当需要求0~某位置的和时，调用sum函数传入这个位置即可，树状数组的代码简洁但是难以理解，所以建议采用背诵的方式，树状数组的实现如下。

  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;
    }

其中c就是辅助数组。需要注意的是树状数组的索引必须从1开始，因此在与题目的输入量相转化时，需要把索引+1作为树状数组的索引。

• 用法举例
  假设我们有数组arr:{1,2,3}，要求部分和，我们先把这些值通过add注入树状数组，一定要注意索引+1.

  for(int i = 0; i < 3; i++){
      add(i+1,arr[i]); // 把arr[i]添加到树状数组的i+1位置
  }

  操作完成后，树状数组就建立好了，下面就可以利用sum来求和了。例如我们需要arr中索引0~2的和，那么使用sum(3)即可，如果要求1~2的和，可以用sum(3)-sum(0)，注意到，sum(0)对于树状数组是一个非法索引，但是通过观察sum函数发现pos=0正好返回0，也就是到这个位置的和为0，满足要求，不必特殊处理。

• 总结
  综上所述，要求arr中i~j的部分和，使用sum(j+1)-sum(i)即可。

• 值的更新问题
  题目还要求使用update函数更新arr中位置i的值为val，这就要利用add函数来实现，注意add函数是在位置pos上追加一个值value，而不是覆盖，因此我们需要计算值的变化量，把它追加到相应位置，并且一定要记得更新arr，否则下次得到的变化量是错误的。

  void update(int i, int val) {
      int ori = m_nums[i]; // m_nums是拷贝arr数组所得的成员变量
      int delta = val - ori;
      m_nums[i] = val;
      add(i+1,delta);
  }

• 具体实现
  通过上面的讨论，解决了每个部分的问题，就可以写出解决此问题的具体代码了，代码如下。

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