摘要：二維表二維表可以將每一對完全映射一個值，這樣的話，空間復雜度變成了，記得我們前面說了，這個數組可能會很大，有個元素，如果用這樣的映射表，內存就溢出了。

給定一個整數數組 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];
    }
  }
})();