题目

题目来源：力扣（LeetCode）

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。

实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], … , nums[j])）

示例：

输入：
[“NumArray”, “sumRange”, “sumRange”, “sumRange”]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

思路分析

解法：树状数组

  1. 根据输⼊数组进⾏初始化，这⾥通过计算前缀和初始化
  2. 在查找数组中某个范围内元素的总和时，分为三种情况：
    • 情况⼀：若mid刚好在sLeft的左侧
    • 情况⼆：若mid刚好在sLeft的右侧
    • 情况三：若mid刚好在 sLeft和sRight中间 然后分别对于三种情况进⾏递归查找
  1. /**
  2.  * @param {number[]} nums
  3.  */
  4. var NumArray = function (nums) {
  5.   this.arrTree = Array(2 * nums.length);
  6.   this.numsArr = nums;
  7.   this.setTree(0, 0, this.numsArr.length - 1);
  8.   // console.log(this.arrTree)
  9. };
  10. NumArray.prototype.setTree = function (i, left, right) {//构建线段树
  11.   if (left > right) return 0;
  12.   if (left == right) {
  13.     this.arrTree[i] = this.numsArr[left];
  14.     return this.arrTree[i];
  15.   }
  16.   let mid = ((left + right) - (left + right) % 2) / 2;
  17.   // 构建i节点的左⼦线段树
  18.   let leftVal = this.setTree(2 * i + 1, left, mid);
  19.   //构建i节点的右⼦线段树
  20.   let rightVal = this.setTree(2 * i + 2, mid + 1, right);
  21.   this.arrTree[i] = leftVal + rightVal;
  22.   return this.arrTree[i];
  23. }
  24. /**
  25.  * @param {number} index
  26.  * @param {number} val
  27.  * @return {void}
  28.  */
  29. NumArray.prototype.update = function (index, val) {// 更新线段树中的值
  30.   this.diff = val - this.numsArr[index];
  31.   this.numsArr[index] = val;
  32.   this.index = index;
  33.   this.updateArrTree(0, 0, this.numsArr.length - 1);
  34.   // console.log(this.arrTree)
  35. };
  36. NumArray.prototype.updateArrTree = function (i, left, right) {
  37.   if (left > right) return;
  38.   if (left == right && left === this.index) {
  39.     this.arrTree[i] += this.diff;
  40.     return;
  41.   }
  43.   // this.arrTree[i] += this.diff;
  44.   this.arrTree[i] += this.diff;
  45.   let mid = ((left + right) - (left + right) % 2) / 2;
  46.   // 如果index⼩于等于mid顺着左⼦树查找，
  47.   if (this.index <= mid) {
  48.     this.updateArrTree(2 * i + 1, left, mid);
  49.   } else {// 否则顺着右⼦树查找
  50.     this.updateArrTree(2 * i + 2, mid + 1, right);
  51.   }
  52. }
  53. /**
  54.  * @param {number} left
  55.  * @param {number} right
  56.  * @return {number}
  57.  */
  58. NumArray.prototype.sumRange = function (left, right) {
  60.   return this.sumArrTree(0, 0, this.numsArr.length - 1, left, right);
  61. };
  62. NumArray.prototype.sumArrTree = function (i, left, right, sLeft, sRight) {
  63.   if (left > sRight || right < sLeft) {
  64.     return 0;
  65.   }
  66.   if (sLeft <= left && sRight >= right) {
  67.     // console.log('a,',this.arrTree[i])
  68.     return this.arrTree[i];
  69.   }
  71.   let mid = ((left + right) - (left + right) % 2) / 2;
  72.   if (sRight <= mid) {// 若mid刚好在sLeft的左侧
  73.     return this.sumArrTree(2 * i + 1, left, mid, sLeft, sRight);
  74.   } else if (sLeft > mid) {// 若mid刚好在sLeft的右侧
  75.     return this.sumArrTree(2 * i + 2, mid + 1, right, sLeft, sRight)
  76.   } else {// 若mid刚好在 sLeft和sRight中间
  77.     return this.sumArrTree(2 * i + 1, left, mid, sLeft, mid) +
  78.       this.sumArrTree(2 * i + 2, mid + 1, right, mid + 1, sRight);
  79.   }
  80. }
  82. /**
  83.  * Your NumArray object will be instantiated and called as such:
  84.  * var obj = new NumArray(nums)
  85.  * var param_1 = obj.sumRange(left,right)
  86.  */