建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
樹(shù)狀數(shù)組（也稱(chēng)為樹(shù)型數(shù)組、二叉索引樹(shù)）是一種常用的數(shù)據(jù)結(jié)構(gòu)，用于高效地維護(hù)一個(gè)數(shù)組的前綴和。在樹(shù)狀數(shù)組中，每個(gè)節(jié)點(diǎn)的值表示該節(jié)點(diǎn)對(duì)應(yīng)的區(qū)間的前綴和，每個(gè)節(jié)點(diǎn)的編號(hào)對(duì)應(yīng)原數(shù)組中對(duì)應(yīng)的下標(biāo)。
巍山網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)公司！從網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、APP開(kāi)發(fā)、成都響應(yīng)式網(wǎng)站建設(shè)公司等網(wǎng)站項(xiàng)目制作，到程序開(kāi)發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)公司公司2013年成立到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來(lái)保證我們的工作的順利進(jìn)行。專(zhuān)注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)公司。
要循環(huán)樹(shù)狀數(shù)組中指定區(qū)間的元素，可以使用樹(shù)狀數(shù)組的查詢(xún)操作。樹(shù)狀數(shù)組查詢(xún)操作的原理是將要查詢(xún)的區(qū)間不斷劃分成長(zhǎng)度為 2 的子區(qū)間，查詢(xún)每個(gè)子區(qū)間對(duì)應(yīng)的節(jié)點(diǎn)的值，然后將它們加起來(lái)即可得到區(qū)間的前綴和。具體操作如下：
- 首先計(jì)算要查詢(xún)的區(qū)間的前綴和，即 sum_right = tree[right]。
- 如果要查詢(xún)的區(qū)間的左端點(diǎn)不為 0，則計(jì)算左端點(diǎn)前一個(gè)位置的前綴和，即 sum_left = tree[left - 1]。
- 最終要查詢(xún)的區(qū)間的和即為 sum_right - sum_left。
下面以一個(gè)例子來(lái)說(shuō)明如何循環(huán)樹(shù)狀數(shù)組中指定區(qū)間的元素。假設(shè)有一個(gè)長(zhǎng)度為 6 的數(shù)組 arr，如下所示：
[1, 3, 5, 7, 9, 11]
現(xiàn)在需要使用樹(shù)狀數(shù)組維護(hù)該數(shù)組的前綴和，并循環(huán)輸出下標(biāo)為 2~4 的元素。具體操作如下：
// 定義樹(shù)狀數(shù)組
const n = 6;
const tree = new Array(n + 1).fill(0);
// 初始化樹(shù)狀數(shù)組
for (let i = 0; i < n; i++) {
update(i, arr[i]);
}
// 循環(huán)輸出下標(biāo)為 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]);
}
// 查詢(xún)指定位置的前綴和
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;
}
}
在上述代碼中，首先定義了一個(gè)長(zhǎng)度為 6 的數(shù)組 arr，并使用樹(shù)狀數(shù)組維護(hù)該數(shù)組的前綴和。然后，定義了要循環(huán)輸出的區(qū)間的左右端點(diǎn) left 和 right，并使用樹(shù)狀數(shù)組查詢(xún)操作計(jì)算出該區(qū)間的前綴和。最后，在循環(huán)中輸出指定區(qū)間的元素。
需要注意的是，在使用樹(shù)狀數(shù)組進(jìn)行區(qū)間查詢(xún)時(shí)，需要先將區(qū)間的前綴和計(jì)算出來(lái)，然后再計(jì)算區(qū)間的和。具體而言，需要計(jì)算出要查詢(xún)的區(qū)間的右端點(diǎn)的前綴和 sum_right，以及左端點(diǎn)前一個(gè)位置的前綴和 sum_left。然后，區(qū)間的和即為 sum_right - sum_left。在實(shí)現(xiàn)查詢(xún)操作時(shí)，可以使用樹(shù)狀數(shù)組的查詢(xún)操作 query 和更新操作 update，具體實(shí)現(xiàn)方式如下：
// 查詢(xún)指定位置的前綴和
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 函數(shù)接受兩個(gè)參數(shù)，分別是要查詢(xún)的位置 idx 和樹(shù)狀數(shù)組 tree，返回指定位置的前綴和。update 函數(shù)接受三個(gè)參數(shù)，分別是要更新的位置 idx、要更新的值 val 和樹(shù)狀數(shù)組 tree，用于更新指定位置的值。
下面以一個(gè)例子來(lái)說(shuō)明如何使用樹(shù)狀數(shù)組循環(huán)指定區(qū)間的元素。假設(shè)有一個(gè)長(zhǎng)度為 10 的數(shù)組 arr，如下所示：
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
現(xiàn)在需要使用樹(shù)狀數(shù)組維護(hù)該數(shù)組的前綴和，并循環(huán)輸出下標(biāo)為 3~7 的元素。具體操作如下：
// 定義樹(shù)狀數(shù)組
const n = 10;
const tree = new Array(n + 1).fill(0);
// 初始化樹(shù)狀數(shù)組
for (let i = 0; i < n; i++) {
update(i, arr[i], tree);
}
// 循環(huán)輸出下標(biāo)為 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}`);
// 查詢(xún)指定位置的前綴和
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;
}
}
在上述代碼中，首先定義了一個(gè)長(zhǎng)度為10 的數(shù)組 arr，然后使用樹(shù)狀數(shù)組維護(hù)該數(shù)組的前綴和。接著，計(jì)算出要查詢(xún)的區(qū)間的前綴和 sum_right 和 sum_left，然后計(jì)算區(qū)間的和 range_sum。最后，使用一個(gè)循環(huán)遍歷區(qū)間中的元素，并輸出每個(gè)元素的值。輸出結(jié)果如下：
4
5
6
7
8
sum_right: 35
sum_left: 6
range_sum: 29
從輸出結(jié)果可以看出，循環(huán)輸出下標(biāo)為 3~7 的元素成功，同時(shí)計(jì)算出了區(qū)間的和 range_sum。
樹(shù)狀數(shù)組是一種高效的數(shù)據(jù)結(jié)構(gòu)，可以用于維護(hù)數(shù)組的前綴和，并支持高效地查詢(xún)區(qū)間和。在實(shí)際應(yīng)用中，可以根據(jù)需要靈活地使用樹(shù)狀數(shù)組實(shí)現(xiàn)各種功能。
分享名稱(chēng)：Javascript樹(shù)狀數(shù)組如何循環(huán)指定區(qū)間的元素
當(dāng)前地址：http://fisionsoft.com.cn/article/codjoip.html
