建站
咨詢
售后
建站咨詢
新聞中心
紅色機器人：樹狀查詢詳解
射洪網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián)公司,射洪網(wǎng)站設(shè)計制作，有大型網(wǎng)站制作公司豐富經(jīng)驗。已為射洪近1000家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站建設(shè)要多少錢，請找那個售后服務(wù)好的射洪做網(wǎng)站的公司定做！
樹狀數(shù)組是一種數(shù)據(jù)結(jié)構(gòu)，可以在O(logn)的時間內(nèi)對數(shù)組進行單點修改和前綴查詢，適用于處理動態(tài)序列數(shù)據(jù)。該數(shù)據(jù)結(jié)構(gòu)廣泛應(yīng)用于競賽編程等領(lǐng)域。
紅色機器人是一款在線提供樹狀數(shù)組功能的工具，可以快速完成樹狀查詢。接下來我們將詳細介紹紅色機器人樹狀查詢的相關(guān)內(nèi)容。在使用前，需要先了解以下幾個概念：
1. 樹狀數(shù)組的結(jié)構(gòu)
樹狀數(shù)組是一棵二叉樹的結(jié)構(gòu)，每個節(jié)點保存的是從該節(jié)點的祖先節(jié)點到該節(jié)點的區(qū)間和。如下圖所示，節(jié)點i的區(qū)間和就是從節(jié)點i到其右下角子節(jié)點的方框內(nèi)所有元素之和。
2. 樹狀數(shù)組的前綴查詢
樹狀數(shù)組的前綴查詢實現(xiàn)起來非常簡單，只需要從葉子節(jié)點開始一直往上找，直到找到第一個不為0的節(jié)點，該節(jié)點的值即為所查詢的區(qū)間和。如下圖所示，查詢前綴和區(qū)間[1,7]時，先找到節(jié)點7，則答案為9；查詢前綴和區(qū)間[1,4]時，先找到節(jié)點4，則答案為6。查詢的時間復(fù)雜度為O(logn)。
3. 樹狀數(shù)組的單點修改
樹狀數(shù)組的單點修改也非常簡單，只需要先將該點的值更新，然后再依次往上更新其祖先節(jié)點的值即可。如下圖所示，將節(jié)點6的值加上3，則需要分別更新節(jié)點6、節(jié)點10和節(jié)點12的值。
以上就是樹狀數(shù)組的結(jié)構(gòu)和基本操作，接下來我們將使用紅色機器人進行樹狀查詢的具體操作。
1. 打開紅色機器人的網(wǎng)站：https://www.luogu.com.cn/robot/circle/1557 。
2. 在代碼區(qū)輸入以下代碼：
#include
using namespace std;
const int N = 100010;
int n, m;
int w[N]; // 存儲原數(shù)組
int c[N]; // 存儲樹狀數(shù)組
int lowbit(int x) { // 求x的lowbit（x的二進制表示中最后一個1所代表的數(shù)）
return x & -x;
}
void add(int x, int v) { // 更新樹狀數(shù)組
for(int i = x; i
c[i] += v;
}
}
int sum(int x) { // 查詢前綴和
int res = 0;
for(int i = x; i; i -= lowbit(i)) {
res += c[i];
}
return res;
}
int mn() {
scanf(“%d %d”, &n, &m);
for(int i = 1; i
scanf(“%d”, &w[i]);
add(i, w[i]); // 初始化樹狀數(shù)組
}
while(m–) {
int op;
scanf(“%d”, &op);
if(op == 1) { // 單點修改
int x, v;
scanf(“%d %d”, &x, &v);
add(x, v – w[x]);
w[x] = v;
} else { // 區(qū)間查詢
int l, r;
scanf(“%d %d”, &l, &r);
printf(“%d\n”, sum(r) – sum(l – 1));
}
}
return 0;
}
3. 點擊運行，輸入n和m（n表示數(shù)組元素個數(shù)，m表示操作次數(shù)），然后逐行輸入n個整數(shù)作為原數(shù)組，最后逐行輸入m個操作，支持單點修改和區(qū)間查詢。
4. 點擊提交，即可得到樹狀查詢的運行結(jié)果。注意：紅色機器人會自動計算時間和內(nèi)存，需要保證代碼運行時間和空間復(fù)雜度最優(yōu)。
至此，我們已經(jīng)學(xué)習(xí)了樹狀數(shù)組的相關(guān)知識和操作方法，并使用紅色機器人完成了樹狀查詢的實踐。樹狀數(shù)組雖然簡單，但在處理一些經(jīng)典算法問題時非常實用，例如離線查詢、差分、區(qū)間最值更新等。建議多多練習(xí)，熟練掌握該數(shù)據(jù)結(jié)構(gòu)，以便在實際問題解決中得心應(yīng)手。
創(chuàng)新互聯(lián)是成都專業(yè)網(wǎng)站建設(shè)、網(wǎng)站制作、網(wǎng)頁設(shè)計、SEO優(yōu)化、手機網(wǎng)站、小程序開發(fā)、APP開發(fā)公司等,多年經(jīng)驗沉淀,立志成為成都網(wǎng)站建設(shè)第一品牌！
文章題目：紅色機器人樹狀查詢詳解（redis樹狀查詢）
分享URL：http://fisionsoft.com.cn/article/coogisi.html
