不可变数组的范围求和

摘要：二维表二维表可以将每一对完全映射一个值，这样的话，空间复杂度变成了，记得我们前面说了，这个数组可能会很大，有个元素，如果用这样的映射表，内存就溢出了。

给定一个整数数组 nums，计算出从第 i 个元素到第 j 个元素的和 ( i ≤ j )，包括 nums[ i ] 和 nums[ j ]。
例子：

const nums = Object.freeze([-2, 0, 3, -5, 2, -1]);

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

注意：

假定数组的值不会改变（如上面代码，nums 因为 Object.freeze 的缘故可读不可写）
sumRange 可能会被使用很多次，求不同范围的值
数组可能规模很大（比如超过 10000 个数），注意运行时间

解题思路

这道题看起来十分简单对吧，简单写一个函数应该谁都会：

const Immutable = Sup => class extends Sup {
  constructor(...args){
    super(...args);
    Object.freeze(this);
  }
}

class NumArray extends Immutable(Array){
  sumRange(i, j){
    let sum = 0;
    for(; i <= j; i++){
      sum += this[i];
    }
    return sum;    
  }
}

上面的代码里面我们重构了数组，这里我用了一点点小技巧来让数组元素不可变，这个技巧在我之前的一篇译文“六个漂亮的 ES6 技巧”中被提到，很多同学不理解那篇文章的第6个技巧，在这里我使用了一下，当然这无关我们今天讨论的主题。

于是我们可以用新的数组对象来计算 sumRange：

var nums = new NumArray(-2, 0, 3, -5, 2, -1);

nums.sumRange(0, 2) -> 1
nums.sumRange(2, 5) -> -1
nums.sumRange(0, 5) -> -3

到这里为止，我们似乎并没有改变什么，我们只是继承了 Array 类，把 sumRange 改成了对象的方法而已，它还是一样很慢。

那接下来我们要怎么做呢？

因为前面说过了，sumRange 要被调用很多次，所以我们要尽可能减少 sumRange 调用的复杂度对吗？按照前面的方式，我们用一个循环来对从 i 到 j 进行求和，有没有更快的方法？答案是：空间换时间，查表！
查表

查表不是查水表，因为 sumRange 要计算很多次，所以我们可以事先在 NumArray 构造的时候将 sumRange 需要查的值算好存入一个表中。

二维表？
R/C 0 1 2 3 4 5
0 -2 -2 1 -4 -2 -3
1 0 3 -2 0 -1
2 3 -2 0 -1
3 -5 -3 -4
4 2 1
5 -1

二维表可以将每一对 i, j 完全映射一个值，这样的话，空间复杂度变成了 O( n2 )，记得我们前面说了，这个数组可能会很大，有 10000 个元素，如果用这样的映射表，内存就溢出了。实际上，使用二维表是愚蠢的，因为我们可以很容易找到以下对应关系：

sumRange(i, j) === sumRange(0, j) - sumRange(0, i - 1); //(i > 0)

一维表

我们只需要将 NumArray 的每一个元素对应从第 1 元素开始求和，将结果保存成一个一维表，我们就可以用 O( 1 ) 时间复杂度来计算 sumRange( i, j ) ！

以下是经过优化之后的 NumArray：

const UniqueID = Sup => class extends Sup {
  constructor(...args){
      super(...args);
      Object.defineProperty(this, "id", {
        value: Symbol(),
        writable: false,
        enumerable: false
      });
    }
}

const Immutable = Sup => class extends Sup {
  constructor(...args){
    super(...args);
    Object.freeze(this);
  }
}

const NumArray = (function(){
  let sumTable = {};
  return class  extends Immutable(UniqueID(Array)){
    constructor(...args){
      super(...args);
      let sum = 0;
      let table = [0];

      for(let i = 0; i < this.length; i++){
        sum += this[i];
        table.push(sum);
      }
      sumTable[this.id] = table;
    }
    sumRange(i, j){
      let table = sumTable[this.id];
      return table[j + 1] - table[i];   
    }
  }
})();

上面的代码里，我们在构造 NumArray 的时候同时创建了一个私有属性 sumTable，它的第 1 个元素是 0，第 i + 1 个元素等于 sumRange(0, i)，因此我们就可以快速通过：

sumRange(i, j){
  let table = sumTable[this.id];
  return table[j + 1] - table[i];   
}

来计算出 sumRange(i, j) 的值了。

进一步优化

上面的代码通过查表大大加快了 sumRange 的执行速度，由于数组 NumArray 是不可变的，因此我们在它被构造的时候创建好 sumTable，那么 sumRange 就完全只需要查表加上一次减法运算就可以完成了。这么做提升了 sumRange 的性能，代价是构造 NumArray 对象的时候带来额外的建表开销。

不过，我们可以不在构造对象的时候建表，而在对象的 sumRange 方法第一次被使用的时候建表。这样的话，我们就将性能开销延从构造对象时迟到了第一次使用 sumRange 时，如果恰巧某种原因，NumArray 对象没有被使用，那么 sumTable 就永远也不会被创建。看下面的代码：

将创建 sumTable 的工作放在 sumRange 第一次被调用时

const UniqueID = Sup => class extends Sup {
  constructor(...args){
    super(...args);
    Object.defineProperty(this, "id", {
      value: Symbol(),
      writable: false,
      enumerable: false
    });
  }
};

const Immutable = Sup => class extends Sup {
  constructor(...args){
    super(...args);
    Object.freeze(this);
  }
};

const NumArray = (function(){
  let sumTable = {};
  return class  extends Immutable(UniqueID(Array)){
    sumRange(i, j){
      if(!sumTable[this.id]){
        let table = [0], sum = 0;
        for(let i = 0; i < this.length; i++){
          sum += this[i];
          table.push(sum);
        }
        sumTable[this.id] = table;
      }
      let table = sumTable[this.id];
      return table[j + 1] - table[i];
    }
  }
})();