基本概念
線段樹(segment tree)也是一種二叉搜索樹掌呜，線段樹的每一個節(jié)點都是一個區(qū)間，葉子節(jié)點則是一個單點區(qū)間详拙，也即
。對于一個非葉子節(jié)點蔓同，其左子節(jié)點的區(qū)間為
饶辙，右子節(jié)點的區(qū)間為
。需要注意的是斑粱，線段樹的區(qū)間是其數(shù)組元素下標(biāo)的區(qū)間弃揽，區(qū)間大小與數(shù)組中元素的大小無關(guān)。
根據(jù)上述定義则北，線段樹任一非根矿微，非葉子節(jié)點的區(qū)間長度都是其父節(jié)點的區(qū)間長度的一半，所以尚揣，線段樹是一個平衡二叉樹涌矢。他的葉子節(jié)點的數(shù)目為N，即整個區(qū)間的長度惑艇。
線段樹的用途很廣蒿辙，主要用于進(jìn)行更新和查詢操作，這里的更新或者查詢一般至少有一個指的是區(qū)間的更新或者查詢滨巴。
線段樹的節(jié)點定義
struct Node{
int l, r, mx;
}tr[MAXN * 4]; //習(xí)慣上將線段樹的大小開到原始數(shù)組的4倍
/*
l : 區(qū)間左端點
r : 區(qū)間右端點
mx : 以l, r為下標(biāo)區(qū)間中元素的最大值
實際上思灌，線段樹數(shù)組足夠的空間==原始數(shù)組n可向上取到的最近的2的某個次方的兩倍
*/
對于一個線段樹數(shù)組來說，某一節(jié)點(編號為d)的左孩子存儲在2 * d恭取， 右孩子存儲在2 * d + 1
- 在c/c++中泰偿，將一個數(shù)乘以2的x次方可以寫成：2 << x，故上面的 " MAXN * 4 " 可以寫成MAXN << 2蜈垮，實際上耗跛，對于 "<<" 和 ">>" 運算符裕照，其實際含義是將左操作數(shù)的二進(jìn)制數(shù)向左或向右移動指定的位數(shù)（比如A == 15，在二進(jìn)制中A的值為：0000 1111调塌，A << 2為：0011 1100）晋南，表現(xiàn)在十進(jìn)制中就是將操作數(shù)乘或除2^x。
建樹
void build(int d, int l, int r){
tr[d].l = l, tr[d].r = r;
if(l == r){
tr[d].mx = arr[l];
return;
}
int mid = (l + r) / 2, lc = d * 2, rc = d * 2 + 1;
build(lc, l, mid);
build(rc, mid + 1, r);
tr[d].mx = max(tr[lc].mx, tr[rc].mx);
}
一般會將更新節(jié)點信息的操作稱為Push或PushUp羔砾，在上述建樹例子中更新節(jié)點信息的操作是：tr[d].mx = max(tr[lc].mx, tr[rc].mx); 一般會將這一句抽離出來寫成一個獨立的函數(shù)：
void Push(int d){
td[d].mx = max(tr[d << 1].mx, tr[d << 1 | 1].mx);
}
查詢
int query(int d, int l, int r){ //查詢一個區(qū)間內(nèi)的最大值
if(tr[d].l == l && tr[d].r == r)return tr[d].mx;
int mid = (tr[d].l + tr[d].r) / 2, lc = d * 2, rc = d * 2 + 1;
if(r <= mid)return query(lc, l, mid);
else if(l > mid)return query(rc, mid, r);
else return max(query(lc, l, mid), query(rc, mid + 1, r));
}
線段樹查詢操作的時間復(fù)雜度可以達(dá)到O(logn)负间，有如下定理：
Thm：當(dāng)n >= 3時，一個的線段樹可以將
的任意子區(qū)間
分解為不超過
個子區(qū)間姜凄。
更新及「慵懶更新」
void modify(int d, int pos, int v){ //將位置為pos的元素更改為v
if(tr[d].l == tr[d].r && tr[d].mx == pos){
tr[d].mx = v;
return;
}
int mid = (tr[d].l + tr[d].r) / 2, lc = d * 2, rc = d * 2 + 1;
if(pos <= mid)modify(lc, pos, v);
else modify(rc, pos, v);
tr[d].mx = max(tr[lc].mx, tr[rc].mx);
}
對于線段樹的更新還有一種「慵懶更新」方式政溃，具體做法是，如果更新的區(qū)間與當(dāng)前節(jié)點的區(qū)間完全重疊态秧，那么就可以只對這個節(jié)點更新董虱，并對這個節(jié)點做標(biāo)記，對這個節(jié)點的子節(jié)點就無需再更新申鱼。若后續(xù)操作中存在關(guān)于這個區(qū)間愤诱，或其子區(qū)間的查詢，那么一定會經(jīng)過這個區(qū)間润讥，當(dāng)再次經(jīng)過這個區(qū)間的時候就更新起子區(qū)間的標(biāo)記转锈，然后置這個區(qū)間的標(biāo)記為"false"即可。下面以hdoj1698為例介紹「慵懶更新」楚殿。
慵懶更新
void update(int L, int R, int val, int d){
if(Tr[d].l == L && Tr[d].r == R){ //區(qū)間完全覆蓋
Tr[d].lazy = val;
return;
}
int mid = Tr[d].l + Tr[d].r >> 1;
if(Tr[d].lazy != 0){ //如果這個區(qū)間被標(biāo)記了就更新其子節(jié)點
Tr[d << 1].lazy = Tr[d << 1 | 1].lazy = Tr[d].lazy;
Tr[d].lazy = 0;
}
if( mid < L )update(L, R, val, d << 1 | 1); //更新右子樹
else if( R <= mid )update(L, R, val, d << 1); //更新左子樹
else update(L, mid, val, d << 1), update(mid + 1, R, val, d << 1 | 1);
}
線段樹習(xí)題
-
慢慢刷吧～
Reference
《ACM/ICPC算法基礎(chǔ)訓(xùn)練教程》
