知識星球（給演演算法愛好者加星標，修煉程式設計內功）
來源：十年蹤跡的部落格
h5jun.com/post/range-sum-query-immutable.html
這是一道翻譯小組的同學問我的題目，這道題很有意思，在 leetcode 上標記的難度為 Easy， 然而正確率出奇地低，只有不到 25%，看來這是一道看似簡單實際上頗有挑戰性的題目。
不可變陣列的範圍求和
給定一個整數陣列 nums，計算出從第 i 個元素到第 j 個元素的和 ( i ≤ j )，包括 nums[ i ] 和 nums[ j ]。
例子：
const nums = Object.freeze([-2, 0, 3, -5, 2, -1]);sumRange(0, 2) -> 1sumRange(2, 5) -> -1sumRange(0, 5) -> -3
註意：
1、假定陣列的值不會改變（如上面程式碼，nums 因為 Object.freeze 的緣故可讀不可寫）
2、sumRange 可能會被使用很多次，求不同範圍的值
3、陣列可能規模很大（比如超過 10000 個數），註意執行時間
解題思路
這道題看起來十分簡單對吧，簡單寫一個函式應該誰都會：
簡單實現
function sumRange(i, j){var sum = 0;for(; i <= j; i++){sum += nums[i];} return sum;}
不過呢，這麼寫，對照上面的註意事項，尤其是後兩條：
- sumRange 可能會被使用很多次
- 陣列的規模可能會很大
如果考慮這兩條，那麼上面的方法可以說是十分慢的，這也是為什麼很多人在 leetcode 提交程式碼通不過，因為簡單這麼算的話，跑 leetcode 的大陣列 case 肯定超時。
那麼，我們要怎麼做才能更快呢？註意到前面說的這是不可變陣列了吧？也就是說陣列初始化完成之後，它的值不會改變，因此我們可以對它進行複製，同時“重新編碼”。
具體怎麼做，大家心裡是不是已經隱隱有答案了？讓我們思考30秒鐘然後繼續 ——
重構陣列
我們可以重新建立一個陣列類，用新的陣列來計算 sumRange：
重構陣列
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) -> 1nums.sumRange(2, 5) -> -1nums.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];}}})();
以上是今天我們討論的內容。上面的程式碼其實還可以最佳化，因為我們將建表的工作推遲到 sumRange 第一次被呼叫時執行，這很好，但這給 sumRange 帶來了一次 if 判斷操作的額外開銷，實際上我們應該也有辦法消除這個開銷，我把這個問題留給大家吧，歡迎大家討論。
朋友會在“發現-看一看”看到你“在看”的內容