搜索
写经验 领红包

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

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

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

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

要循环树状数组中指定区间的元素,可以使用树状数组的查询操作。树状数组查询操作的原理是将要查询的区间不断划分成长度为 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。

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

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