基本概念
線段樹(segment tree)也是一種二叉搜索樹，線段樹的每一個(gè)節(jié)點(diǎn)都是一個(gè)區(qū)間，葉子節(jié)點(diǎn)則是一個(gè)單點(diǎn)區(qū)間，也即
。對(duì)于一個(gè)非葉子節(jié)點(diǎn)，其左子節(jié)點(diǎn)的區(qū)間為
，右子節(jié)點(diǎn)的區(qū)間為
。需要注意的是，線段樹的區(qū)間是其數(shù)組元素下標(biāo)的區(qū)間，區(qū)間大小與數(shù)組中元素的大小無關(guān)。
根據(jù)上述定義，線段樹任一非根，非葉子節(jié)點(diǎn)的區(qū)間長度都是其父節(jié)點(diǎn)的區(qū)間長度的一半，所以，線段樹是一個(gè)平衡二叉樹。他的葉子節(jié)點(diǎn)的數(shù)目為N，即整個(gè)區(qū)間的長度。
線段樹的用途很廣，主要用于進(jìn)行更新和查詢操作，這里的更新或者查詢一般至少有一個(gè)指的是區(qū)間的更新或者查詢。
線段樹的節(jié)點(diǎn)定義
struct Node{
int l, r, mx;
}tr[MAXN * 4]; //習(xí)慣上將線段樹的大小開到原始數(shù)組的4倍
/*
l : 區(qū)間左端點(diǎn)
r : 區(qū)間右端點(diǎn)
mx : 以l, r為下標(biāo)區(qū)間中元素的最大值
實(shí)際上，線段樹數(shù)組足夠的空間==原始數(shù)組n可向上取到的最近的2的某個(gè)次方的兩倍
*/
對(duì)于一個(gè)線段樹數(shù)組來說，某一節(jié)點(diǎn)(編號(hào)為d)的左孩子存儲(chǔ)在2 * d， 右孩子存儲(chǔ)在2 * d + 1
- 在c/c++中，將一個(gè)數(shù)乘以2的x次方可以寫成：2 << x，故上面的 " MAXN * 4 " 可以寫成MAXN << 2，實(shí)際上，對(duì)于 "<<" 和 ">>" 運(yùn)算符，其實(shí)際含義是將左操作數(shù)的二進(jìn)制數(shù)向左或向右移動(dòng)指定的位數(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);
}
一般會(huì)將更新節(jié)點(diǎn)信息的操作稱為Push或PushUp，在上述建樹例子中更新節(jié)點(diǎn)信息的操作是：tr[d].mx = max(tr[lc].mx, tr[rc].mx); 一般會(huì)將這一句抽離出來寫成一個(gè)獨(dú)立的函數(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){ //查詢一個(gè)區(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));
}
線段樹查詢操作的時(shí)間復(fù)雜度可以達(dá)到O(logn)，有如下定理：
Thm：當(dāng)n >= 3時(shí)，一個(gè)的線段樹可以將
的任意子區(qū)間
分解為不超過
個(gè)子區(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);
}
對(duì)于線段樹的更新還有一種「慵懶更新」方式，具體做法是，如果更新的區(qū)間與當(dāng)前節(jié)點(diǎn)的區(qū)間完全重疊，那么就可以只對(duì)這個(gè)節(jié)點(diǎn)更新，并對(duì)這個(gè)節(jié)點(diǎn)做標(biāo)記，對(duì)這個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)就無需再更新。若后續(xù)操作中存在關(guān)于這個(gè)區(qū)間，或其子區(qū)間的查詢，那么一定會(huì)經(jīng)過這個(gè)區(qū)間，當(dāng)再次經(jīng)過這個(gè)區(qū)間的時(shí)候就更新起子區(qū)間的標(biāo)記，然后置這個(gè)區(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){ //如果這個(gè)區(qū)間被標(biāo)記了就更新其子節(jié)點(diǎn)
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)練教程》
