- 【用途】多次查詢區間 [L, R] 的某些資訊,如「區間和」或「區間最大值」。 亦可同時紀錄多種資訊。 資料可以修改 (單點修改或區間修改)。
- 【條件】要查詢的資訊需滿足「結合律」。
- 【實作】
- 二元樹資料結構 (根節點編號為1)。
- 每個節點存一段連續區間 [L, R] 的資訊(e.g. 區間和),如節點 [1, 2] 存放A1 + A2。
- 根節點存放區間 [1, n] 的資訊。(下圖假設有n = 9筆資料)
- 節點編號:每個點的左兒子的節點編號為 x*2 (x<<1) ,右兒子則為 x * 2 + 1 (x<<1|1) 。
- 陣列 total[n << 2]:存放每段區間的數字總和(開4倍陣列避免溢位。)
- build( ):建立線段樹,左子樹紀錄區間 [L, mid],右子樹紀錄區間 [mid+1, R]。
- pull( ):合併左節點與右節點的值。
- query( ):查詢對應區間 [ql, qr] 的值。
- update( ):更新單點 (位置pos) 的值 (val),所有重疊的區間都要一併更新。
- 【練習】HDU 1166. 敌兵布阵【題解】

//total:線段樹的每個節點,用來紀錄區間和
//開4倍陣列避免溢位
int total[50005 << 2];
void pull(int x){
//合併左節點與右節點
total[x] = total[x<<1] + total[x<<1|1];
}
void build(int x, int l, int r){
if (l == r){
cin >> total[x];
return;
}
int mid = (l+r) >> 1;
build(x<<1, l, mid);
build(x<<1|1, mid+1, r);
pull(x);
}

int query(int x, int l, int r, int ql, int qr){
//[ql, qr]: 查詢區間
if (ql <= l && qr >= r){
return total[x];
}
int ret = 0;
int mid = (l+r)>>1;
if (ql <= mid){
ret += query(x<<1, l, mid, ql, qr);
}
if (qr > mid){
ret += query(x<<1|1, mid+1, r, ql, qr);
}
return ret;
}
void update(int x, int l, int r, int pos, int val){
if (l == r){
total[x] += val;
return;
}
int mid = (l+r) >> 1;
if (pos <= mid) update(x<<1, l, mid, pos, val);
else update(x<<1|1, mid+1, r, pos, val);
pull(x);
}
【更多練習】HDU 1754. I Hate It【題解】
【更多練習】HDU 3308. LCIS【題解】
【更多練習】HDU 4027. Can you answer these queries?【題解】