- 【用途】多次查詢區間 [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?【題解】