js树状结构(js树形数据结构)

导语：每日分享- javascript树状数组如何循环指定区间的元素

树状数组（也称为树型数组、二叉索引树）是一种常用的数据结构，用于高效地维护一个数组的前缀和。在树状数组中，每个节点的值表示该节点对应的区间的前缀和，每个节点的编号对应原数组中对应的下标。

要循环树状数组中指定区间的元素，可以使用树状数组的查询操作。树状数组查询操作的原理是将要查询的区间不断划分成长度为 2 的子区间，查询每个子区间对应的节点的值，然后将它们加起来即可得到区间的前缀和。具体操作如下：

首先计算要查询的区间的前缀和，即 sum_right = tree[right]。如果要查询的区间的左端点不为 0，则计算左端点前一个位置的前缀和，即 sum_left = tree[left - 1]。最终要查询的区间的和即为 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。最后，使用一个循环遍历区间中的元素，并输出每个元素的值。输出结果如下：

45678sum_right: 35sum_left: 6range_sum: 29

从输出结果可以看出，循环输出下标为 3~7 的元素成功，同时计算出了区间的和 range_sum。

树状数组是一种高效的数据结构，可以用于维护数组的前缀和，并支持高效地查询区间和。在实际应用中，可以根据需要灵活地使用树状数组实现各种功能。

本文内容由快快网络小故创作整理编辑！