本帖最後由 李知易 於 2024-11-26 22:47 編輯
特色：線段樹是一種二元樹形的資料結構，可以快速查詢結構內包含某一點的所有區間
常見應用：點修改、區間修改、區間查詢（區間求和，求區間最大值，求區間最小值）
建構線段樹：
(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的右子節點);
} |
