每日分享- javascript樹狀數組如何循環指定區間的元素

樹狀數組（也稱為樹型數組、二叉索引樹）是一種常用的資料結構，用于高效地維護一個數組的字首和。在樹狀數組中，每個節點的值表示該節點對應的區間的字首和，每個節點的編号對應原數組中對應的下标。

要循環樹狀數組中指定區間的元素，可以使用樹狀數組的查詢操作。樹狀數組查詢操作的原理是将要查詢的區間不斷劃分成長度為 2 的子區間，查詢每個子區間對應的節點的值，然後将它們加起來即可得到區間的字首和。具體操作如下：

1. 首先計算要查詢的區間的字首和，即 sum_right = tree[right]。
2. 如果要查詢的區間的左端點不為 0，則計算左端點前一個位置的字首和，即 sum_left = tree[left - 1]。
3. 最終要查詢的區間的和即為 sum_right - sum_left。

下面以一個例子來說明如何循環樹狀數組中指定區間的元素。假設有一個長度為 6 的數組 arr，如下所示：

[1, 3, 5, 7, 9, 11]           

現在需要使用樹狀數組維護該數組的字首和，并循環輸出下标為 2~4 的元素。具體操作如下：

// 定義樹狀數組
const n = 6;
const tree = new Array(n + 1).fill(0);

// 初始化樹狀數組
for (let i = 0; i < n; i++) {
  update(i, arr[i]);
}

// 循環輸出下标為 2~4 的元素
const left = 2;
const right = 4;
let sum_right = query(right, tree);
let sum_left = left > 0 ? query(left - 1, tree) : 0;

for (let i = left; i <= right; i++) {
  console.log(arr[i]);
}

// 查詢指定位置的字首和
function query(idx, tree) {
  let sum = 0;
  while (idx > 0) {
    sum += tree[idx];
    idx -= idx & -idx;
  }
  return sum;
}

// 更新指定位置的值
function update(idx, val) {
  idx++;
  while (idx <= n) {
    tree[idx] += val;
    idx += idx & -idx;
  }
}           

在上述代碼中，首先定義了一個長度為 6 的數組 arr，并使用樹狀數組維護該數組的字首和。然後，定義了要循環輸出的區間的左右端點 left 和 right，并使用樹狀數組查詢操作計算出該區間的字首和。最後，在循環中輸出指定區間的元素。

需要注意的是，在使用樹狀數組進行區間查詢時，需要先将區間的字首和計算出來，然後再計算區間的和。具體而言，需要計算出要查詢的區間的右端點的字首和 sum_right，以及左端點前一個位置的字首和 sum_left。然後，區間的和即為 sum_right - sum_left。在實作查詢操作時，可以使用樹狀數組的查詢操作 query 和更新操作 update，具體實作方式如下：

// 查詢指定位置的字首和
function query(idx, tree) {
  let sum = 0;
  while (idx > 0) {
    sum += tree[idx];
    idx -= idx & -idx;
  }
  return sum;
}

// 更新指定位置的值
function update(idx, val, tree) {
  idx++;
  while (idx <= n) {
    tree[idx] += val;
    idx += idx & -idx;
  }
}           

其中，query 函數接受兩個參數，分别是要查詢的位置 idx 和樹狀數組 tree，傳回指定位置的字首和。update 函數接受三個參數，分别是要更新的位置 idx、要更新的值 val 和樹狀數組 tree，用于更新指定位置的值。

下面以一個例子來說明如何使用樹狀數組循環指定區間的元素。假設有一個長度為 10 的數組 arr，如下所示：

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];           

現在需要使用樹狀數組維護該數組的字首和，并循環輸出下标為 3~7 的元素。具體操作如下：

// 定義樹狀數組
const n = 10;
const tree = new Array(n + 1).fill(0);

// 初始化樹狀數組
for (let i = 0; i < n; i++) {
  update(i, arr[i], tree);
}

// 循環輸出下标為 3~7 的元素
const left = 3;
const right = 7;
let sum_right = query(right, tree);
let sum_left = left > 0 ? query(left - 1, tree) : 0;
let range_sum = sum_right - sum_left;

for (let i = left; i <= right; i++) {
  console.log(arr[i]);
}

console.log(`sum_right: ${sum_right}`);
console.log(`sum_left: ${sum_left}`);
console.log(`range_sum: ${range_sum}`);

// 查詢指定位置的字首和
function query(idx, tree) {
  let sum = 0;
  while (idx > 0) {
    sum += tree[idx];
    idx -= idx & -idx;
  }
  return sum;
}

// 更新指定位置的值
function update(idx, val, tree) {
  idx++;
  while (idx <= n) {
    tree[idx] += val;
    idx += idx & -idx;
  }
}           

在上述代碼中，首先定義了一個長度為10 的數組 arr，然後使用樹狀數組維護該數組的字首和。接着，計算出要查詢的區間的字首和 sum_right 和 sum_left，然後計算區間的和 range_sum。最後，使用一個循環周遊區間中的元素，并輸出每個元素的值。輸出結果如下：

4
5
6
7
8
sum_right: 35
sum_left: 6
range_sum: 29           

從輸出結果可以看出，循環輸出下标為 3~7 的元素成功，同時計算出了區間的和 range_sum。

樹狀數組是一種高效的資料結構，可以用于維護數組的字首和，并支援高效地查詢區間和。在實際應用中，可以根據需要靈活地使用樹狀數組實作各種功能。