種子論壇 | 高雄市資訊培育協會學員討論區

標題: 線段樹Segment Tree [打印本頁]

作者: 李知易 時間: 2024-11-26 22:42 標題: 線段樹Segment Tree

本帖最後由李知易於 2024-11-26 22:47 編輯

[attach]20252[/attach]
特色：線段樹是一種二元樹形的資料結構，可以快速查詢結構內包含某一點的所有區間
常見應用：點修改、區間修改、區間查詢（區間求和，求區間最大值，求區間最小值）
建構線段樹：
(pseudo code)
array segment_tree; //用來存線段樹的那個陣列，用普通陣列或vector都可
array a; //序列
int n; //a的大小

//v的區間是[L,R]
void build(int L, int R, vertex v){
if(L == R){
segment_tree[v] = 用a[L]得出答案;
return;
}
int M = (L + R) / 2;
//把區間二等分
build(L, M, v的左子節點);
build(M + 1, R, v的右子節點);
}

歡迎光臨種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/)