背景

了解到二叉索引樹這個數據結構，是在 leetcode 的 307 題，題目是要求實現一個數據結構，可以返回數組任意區間的和以及更新數組的某個值。

307、Range Sum Query - MutableGiven 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) -> 9update(1, 2)sumRange(0, 2) -> 8Constraints:- The array is only modifiable by the update function. - You may assume the number of calls to update and sumRange function is distributed evenly. - 0 <= i <= j <= nums.length - 1

常規解法

先介紹下常規的解法，樹狀數組有用到他們之中的一些思想或者過程。

解法一

最暴力的解法，sumRange 直接 for 循環算，update 直接更新數組中的值。

/*** @param {number[]} nums*/ var NumArray = function (nums) {this.nums = [...nums]; };/*** @param {number} i* @param {number} val* @return {void}*/ NumArray.prototype.update = function (i, val) {this.nums[i] = val; };/*** @param {number} i* @param {number} j* @return {number}*/ NumArray.prototype.sumRange = function (i, j) {let sum = 0;for (let k = i; k <= j; k++) {sum += this.nums[k];}return sum; };/*** Your NumArray object will be instantiated and called as such:* var obj = new NumArray(nums)* obj.update(i,val)* var param_2 = obj.sumRange(i,j)*/

時間復雜度： update 是 O(1)，sumRange 是 O(n)。

解法二

303 題 做過 sumRange 的優化，我們用一個數組保存累計的和，numsAccumulate[i] 存儲 0 到 i - 1 累計的和。

如果我們想求 i 累積到 j 的和，只需要用 numsAccumulate[j + 1] 減去 numsAccumulate[i]。

結合下邊的圖應該很好理解，我們要求的是橙色部分，相當于 B 的部分減去 A 的部分。

所以我們可以提前把一些前綴和存起來，然后查詢區間和的時候在可以通過差實現。

/*** @param {number[]} nums*/ var NumArray = function (nums) {this.nums = [...nums];this.numsAccumulate = [0];let sum = 0;for (let i = 0; i < nums.length; i++) {sum += nums[i];this.numsAccumulate.push(sum);} };/*** @param {number} i* @param {number} val* @return {void}*/ NumArray.prototype.update = function (i, val) {let sub = val - this.nums[i];this.nums[i] = val;for (let k = i + 1; k < this.numsAccumulate.length; k++) {this.numsAccumulate[k] += sub;} };/*** @param {number} i* @param {number} j* @return {number}*/ NumArray.prototype.sumRange = function (i, j) {return this.numsAccumulate[j + 1] - this.numsAccumulate[i]; };/*** Your NumArray object will be instantiated and called as such:* var obj = new NumArray(nums)* obj.update(i,val)* var param_2 = obj.sumRange(i,j)*/

時間復雜度： update 是 O(n)，sumRange 是 O(1)。

雖然 sumRange 的時間復雜度優化了，但是 update 又變成了 O(n)。因為更新一個值的時候，這個值后邊的累計和都需要更新。

解法三

解法一和解法二時間復雜度兩個方法始終一個是 O(1)，一個是 O(n)。這里再分享 官方題解 提供的一個解法，可以優化查詢區間的時間復雜度。

我們可以將原數據分成若干個組，然后提前計算這些組的和，舉個例子。

組號: 0 1 2 3 數組: [2 4 5 6] [9 9 3 8] [1 2 3 4] [4 2 3 4] 下標: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 和: 17 29 10 13

如果我們要計算 sumRange(1,13)，之前我們需要循環累加下標 1 到 13 的數字的和。

現在我們只需要循環累加 1 到 3 的和，加上循環累加 12 到 13 的和，再累加中間組提前算好的和，也就是第 1 組和第 2 組的和 29 和 10 ，就是最終的結果了。

至于更新的話，我們也不需要像解法二那樣更新那么多。我們只需要更新當前元素所在的組即可。

下一個問題，每組的大小定多少呢？

如果定的小了，那么組數就會特別多。

如果定的大了，那么組內元素就會特別多。

組數和組內元素個數都會影響到 sumRange 的時間復雜度。

這里，我們在組數和組內元素個數之間取個平衡，假設數組大小是 n，那么組內元素個數取

，這樣的話組數也是 ，這樣就可以保證我們查詢的時間復雜度是 了。因為最壞的情況，無非是查詢范圍跨越整個數組，中間我們需要累加 個組，第 0 組最多累加 次，最后一組也最多累加 次，整體上就是 了。

結合代碼理解一下。

/*** @param {number[]} nums*/ var NumArray = function (nums) {this.nums = [...nums];this.groupSize = Math.floor(Math.sqrt(this.nums.length));this.group = [];let sum = 0;let i = 0;for (i = 0; i < nums.length; i++) {sum += nums[i];if ((i + 1) % this.groupSize === 0) {this.group.push(sum);sum = 0;}}//有可能數組大小不能整除組的大小, 最后會遺漏下幾個元素if (i % this.groupSize !== 0) {this.group.push(sum);} };/*** @param {number} i* @param {number} val* @return {void}*/ NumArray.prototype.update = function (i, val) {let sub = val - this.nums[i];let groudId = Math.floor(i / this.groupSize);this.group[groudId] += sub;this.nums[i] = val; };/*** @param {number} i* @param {number} j* @return {number}*/ NumArray.prototype.sumRange = function (i, j) {let groupI = Math.floor(i / this.groupSize);let groupJ = Math.floor(j / this.groupSize);let sum = 0;//在同一組內, 直接累加if (groupI === groupJ) {for (let k = i; k <= j; k++) {sum += this.nums[k];}} else {//左邊組的元素累加for (let k = i; k < (groupI + 1) * this.groupSize; k++) {sum += this.nums[k];}//累加中間所有的組for (let g = groupI + 1; g < groupJ; g++) {sum += this.group[g];}//右邊組的元素累加for (let k = groupJ * this.groupSize; k <= j; k++) {sum += this.nums[k];}}return sum; };/*** Your NumArray object will be instantiated and called as such:* var obj = new NumArray(nums)* obj.update(i,val)* var param_2 = obj.sumRange(i,j)*/

時間復雜度： update 是 O(1)，sumRange 是

。

樹狀數組

有了上邊的背景，我們再回到樹狀數組。

這個解法寫法很簡單，但理解的話可能稍微難一些，很多文章都直接講該怎么用，沒有介紹最初的動機，于是去看了提出這個解法的 原始論文，看看能不能理解。

這個解法叫 Fenwick tree 或者binary indexed tree，翻譯過來的話叫做樹狀數組或者二叉索引樹，但我覺得 binary 翻譯成二進制更好，叫做二進制索引樹更貼切些，二叉樹容易引起誤解。

回想一下解法三，我們預先求出了若干個區間和，然后查詢的區間可以根據之前預先求出來的區間來求出。這里的話同樣的思想，先預先求一些區間和，然后把要求的區間分解成若干個之前求好的區間和即可。相比于解法三，這里的分解會更加巧妙一些。

我們知道計算機中的數都是由二進制來表示的，任何一個數都可以分解成 2 的冪次的和，進制轉換不熟的話可以參考 再談進制轉換。

舉個例子

， 等等。

接下來就是神奇的地方了，每一個數都可以拆成這樣的 x = a + b + c + ... 的形式。

我們把等式左側的數 x 看做是區間 [1, x]，等式右邊看做從 x 開始每個區間的長度，也就變成了下邊的樣子。

[1, x] = [x, x - a + 1] + [x - a, x - a - b + 1] + [x - a - b, x - a - b - c + 1] + ...。

看起來有些復雜，舉個具體的例子就簡單多了。

以

為例，可以轉換為下邊的等式。

[1, 11] = [11, 11] + [10, 9] + [8, 1]。

[11, 11]、[10, 9]、[8, 1] 長度分別是 1、2、8。

我們成功把一個大區間，分成了若干個小區間，這就是樹狀數組最核心的地方了，只要理解了上邊講的，下邊就很簡單了。

首先，因為數組的下標是從 0 開始的，上邊的區間范圍是從 1 開始的，所以我們在原數組開頭補一個 0 ，這樣區間就是從 1 開始了。

因此我們可以通過分解快速的求出 [1, x] 任意前綴區間的和，知道了前綴區間的和，就回到了解法二，通過做差可以算出任意區間的和了。

最后，我們需要解決子區間該怎么求？

[1, 11] = [11, 11] + [10, 9] + [8, 1] 我們用 V 表示子區間，用 F 表示某個區間。

F[1,11] = V[11] + V[10] + V[8]

其中，V[11] = F[11,11], V[10] = F[10,9], V[8]=F[8...1]，為什么是這樣？

回到二進制，F[0001,1011] = V[1011] + V[1010] + V[1000]

1010 = 1011 - 0001，0001 就是十進制的 1，所以 V[1011] 存 1 個數，所以 V[11] = F[11,11]。

1000 = 1010 - 0010，0010 就是十進制的 2，所以 V[1010] 存 2 個數，所以 V[10] = F[10,9]。

0000 = 1000 - 1000，1000 就是十進制的 8，所以 V[1000] 存 8 個數，所以 V[8] = F[8...1]。

V[1011] 存 1 個數， V[1010] 存 2 個數，看的是二進制最右邊的一個 1 到末尾的大小。1010 就是 10，1000 就是 1000 。

怎么得到一個數最右邊的 1 到末尾的大小，是二進制操作的一個技巧，會用到一些補碼的知識，可以參考 趣談計算機補碼。

將原數取反，然后再加 1 得到的新數和原數按位相與就得到了最右邊的 1 到末尾的數。

舉個例子，對于 101000 ，先取反得到 010111，再加 1 變成 011000，再和原數相與，101000 & 011000，剛好就得到了 1000。其中，取反再加一，根據補碼的知識，可以通過取相反數得到。

所以對于 i 的話，i & -i 就得到了最右邊的 1 到末尾的數，也就是 V[i] 這個區間存多少個數。

如果 len = i & -i ，那么 V[i] = F[i,i-1,i-2, ... i-len+1]。

參考下邊的代碼，BIT 就是我們上邊要求的 V 數組。

/*** @param {number[]} nums*/ var NumArray = function (nums) {this.nums = [0, ...nums]; //補一個 0this.BIT = new Array(this.nums.length);for (let i = 1; i < this.BIT.length; i++) {let index = i - ( i & -i ) + 1;this.BIT[i] = 0;//累加 index 到 i 的和while (true) {this.BIT[i] += this.nums[index];index += 1;if (index > i) {break;}}} };

有了 BIT 這個數組，一切就都好說了。如果我們想求 F[1, 11] 也就是前 11 個數的和。

F[1,11] = BIT[11] + BIT[10] + BIT[8]，看下二進制 BIT[0001,1011] = BIT[1011] + BIT[1010] + BIT[1000] 。

1011 -> 1010 -> 1000，對于 BIT 每次的下標就是依次把當前數最右邊的 1 變成 0 。

這里有兩種做法，一種是我們求出當前數最右邊的 1 到末尾的數，然后用原數減一下。

舉個例子， 1010 最右邊的 1 到末尾的數是 10 ，然后用 1010 - 10 就得到 1000 了。

另外一種做法，就是 n & (n - 1)，比如 1010 & (1010 - 1)，剛好就是 1000 了。

知道了這個，我們可以實現一個函數，用來求區間 [1, n] 的和。

NumArray.prototype.range = function (index) {let sum = 0;while (index > 0) {sum += this.BIT[index];index -= index & -index;//index = index & (index - 1); //這樣也可以}return sum; };

有了 range 函數，題目中的 sumRange 也就很好實現了。

NumArray.prototype.sumRange = function (i, j) {//range 求的區間范圍下標是從 1 開始的,所以這里的 j 需要加 1return this.range(j + 1) - this.range(i); };

接下來是更新函數怎么寫。

更新函數的話，最關鍵的就是找出，當我們更新數組第 i 個值，會影響到我們的哪些子區間，也就是代碼中的 BIT 數組需要更新哪些。

我們來回憶下之前做了什么事情。

這是論文中的一張圖，含義就是我們之前分析的，BIT[8] 存的是 F[1...8] ，對應圖中的就是從第 8 個位置到第 1 個位置的矩形。BIT[6] 存的是 F[6,5]， 對應圖中的就是從第 6 個位置一直到第 5 個位置的矩形。

然后我們水平從某個數畫一條線，比如從 3 那里畫一條線。

穿過了 3 對應的矩形，4 對應的矩形，8 對應的矩形。因此如果改變第 3 個數，BIT[3]，BIT[4] 以及 BIT[8] 就需要更新。通過這種方式我們把每個數會影響到哪個區間畫出來，找一下規律。

當改變了第 5 個元素的時候，會依次影響到 BIT[5]，BIT[6]，BIT[8]，BIT[16]。

00101 -> 00110 -> 01000 -> 10000。

00101 + 1 = 00110。

00110 + 10 = 01000

01000 + 1000 = 10000

可以看到每次都是加上當前數最右邊的 1 到末尾的數，即 next = current + (current & -current)。

所以更新的代碼也就出來了。

/*** @param {number} i* @param {number} val* @return {void}*/ NumArray.prototype.update = function (i, val) {i += 1;//對應的下標要進行加 1const sub = val - this.nums[i];this.nums[i] = val;while (i < this.nums.length) {this.BIT[i] += sub;i += i & -i;} };

綜上，這道題就解決了，我們把代碼合在一起。

/*** @param {number[]} nums*/ var NumArray = function (nums) {this.nums = [0, ...nums];this.BIT = new Array(this.nums.length);for (let i = 1; i < this.BIT.length; i++) {let index = i - ( i & -i ) + 1;this.BIT[i] = 0;while (true) {this.BIT[i] += this.nums[index];index += 1;if (index > i) {break;}}} };/*** @param {number} i* @param {number} val* @return {void}*/ NumArray.prototype.update = function (i, val) {i += 1;const sub = val - this.nums[i];this.nums[i] = val;while (i < this.nums.length) {this.BIT[i] += sub;i += i & -i;} }; /*** @param {number} i* @param {number} j* @return {number}*/ NumArray.prototype.sumRange = function (i, j) {return this.range(j + 1) - this.range(i); };NumArray.prototype.range = function (index) {let sum = 0;while (index > 0) {sum += this.BIT[index];// index -= index & -index;index = index & (index - 1); //這樣也可以}return sum; };/*** Your NumArray object will be instantiated and called as such:* var obj = new NumArray(nums)* obj.update(i,val)* var param_2 = obj.sumRange(i,j)*/

時間復雜度的話，初始化、更新、查詢其實都和二進制的位數有關，以查詢為例。每次將二進制的最后一位變成 0，最壞的情況就是初始值是全 1，即 1111 這種，執行次數就是 4 次，也就是二進制的位數。

如果是 n ，那么位數大約就是 log(n)，可以結合 再談進制轉換 理解。把一個數展開為 2 的冪次和，位數其實就是最高位的冪次加 1。比如

，最高冪次是 3 ，所以 11 的二進制(1011) 位數就是 4。如果要求的數是 n，最高的次冪是 x ， ，近似一下 ，x = log(n)，位數就是 log(n) + 1。

所以 update 和 sumRange 的時間復雜度就是 O(log(n))。

對于初始化函數，因為要執行 n 次，所以就是 O(nlog(n))。當然我們也可以利用解法二，把前綴和都求出來，然后更新數組 BIT 的每個值，這樣就是 O(n) 了。但不是很有必要，因為如果查詢和更新的次數很多，遠大于 n 次，那么初始化這里的時間復雜度也就無關緊要了。

總

講了很多，其實樹狀數組最根本的就是開頭所提到的二進制冪次的分解，

，然后把右邊的分解出來的數看做子區間的長度。

總結

以上是生活随笔為你收集整理的下拉菜单实现树状结构_二叉索引树（树状数组）的原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。