線段樹(shù)是所有數(shù)據(jù)結(jié)構(gòu)中，最常用的之一。線段樹(shù)的功能多樣，既可以代替樹(shù)狀數(shù)組完成“區(qū)間和”查詢，也可以完成一些所謂“動(dòng)態(tài)RMQ”（可修改的區(qū)間最值問(wèn)題）的操作。其中，它們大部分都是由遞歸實(shí)現(xiàn)的，因此就有一些問(wèn)題——棧空間占用大和常數(shù)大。
因此，從中便衍生了一種非遞歸式的線段樹(shù)（作者是THU的張昆瑋，參見(jiàn)他自己的PPT講稿《統(tǒng)計(jì)的力量-線段樹(shù)》），命名為zkw線段樹(shù)。
以下內(nèi)容均用zkw線段樹(shù)保存區(qū)間最大值作為演示。
1、建樹(shù)
我們可以先觀察左邊面這張圖。這張圖本來(lái)是一張堆式的樹(shù)形圖，這里把它轉(zhuǎn)化成了二進(jìn)制。從中，我們可以發(fā)現(xiàn)最底層的節(jié)點(diǎn)舍去最低位，也就是說(shuō)向右移一位之后，就變成了他們的父節(jié)點(diǎn)。同理，第二層中的結(jié)點(diǎn)也可以通過(guò)相同的方式變成根節(jié)點(diǎn)。
因此，我們?cè)跇?gòu)建這棵樹(shù)時(shí)，就可以利用計(jì)算機(jī)的二進(jìn)制建樹(shù)，達(dá)到快速簡(jiǎn)單的目的。（不知道大家有沒(méi)有聽(tīng)說(shuō)過(guò)一句話，寫(xiě)程序要保持短而簡(jiǎn)單——Keep it short ans simple，KISS）。
zkw線段樹(shù)的操作幾乎沒(méi)有出現(xiàn)遞歸，而是用循環(huán)代替。例如建樹(shù)操作（d數(shù)組存儲(chǔ)數(shù)值）：
void build(int n)
{ for(bit=1;bit<=n+1;bit<<=1); for(int i=bit+1;i<=bit+n;i++)
scanf("%d",&d[i]); for(int i=bit-1;i;i--)
d[i]=max(d[i<<1],d[i<<1|1]); //i<<1|1 = (i<<1)+1 = 2*i+1}
（這里解釋一下，bit表示非葉子節(jié)點(diǎn)，即倒二層及以上的節(jié)點(diǎn)數(shù)，每個(gè)節(jié)點(diǎn)保存的是它的值，如：和，最大值，最小值……）
而普通的線段樹(shù)建樹(shù)則類似于（代碼來(lái)自這里）：
struct SegTreeNode
{ int val;
}segTree[MAXNUM];//定義線段樹(shù)void build(int root, int arr[], int istart, int iend)
{ if(istart == iend)//葉子節(jié)點(diǎn)
segTree[root].val = arr[istart]; else
{ int mid = (istart + iend) / 2;
build(root*2+1, arr, istart, mid);//遞歸構(gòu)造左子樹(shù)
build(root*2+2, arr, mid+1, iend);//遞歸構(gòu)造右子樹(shù) //根據(jù)左右子樹(shù)根節(jié)點(diǎn)的值，更新當(dāng)前根節(jié)點(diǎn)的值
segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
}
}
很簡(jiǎn)單的例子，說(shuō)明了zkw線段樹(shù)不僅不需要遞歸，而且在代碼上也更簡(jiǎn)潔。
2、普通操作
既然是線段樹(shù)，那么就肯定能完成修改與查詢操作。
2.1 單點(diǎn)修改——二進(jìn)制思想的運(yùn)用
單點(diǎn)修改也不難，他的思想就是先把葉節(jié)點(diǎn)修改，然后依次維護(hù)父節(jié)點(diǎn)（把所有和它有關(guān)的的修改掉）。例如這樣：
void update(int x,int y)
{ for(d[x+=bit]=y,x>>=1;x;x>>=1)
d[x]=max(d[x<<1],d[x<<1|1]);
}這個(gè)代碼就更為簡(jiǎn)短了（這里就不拿出來(lái)對(duì)比了）。
當(dāng)然，如果不是整個(gè)修改，而是加上或減去某數(shù)，只需要將for循環(huán)中的 d[x+=bit]=y 改為 d[x+=bit]+=y 即可（這里統(tǒng)一用整體修改作示范，下同）。
2.2 單點(diǎn)查詢——最簡(jiǎn)單的查詢
假設(shè)數(shù)組中有 x 個(gè)元素，二叉樹(shù)層數(shù)為 m，那么這 x 個(gè)元素在這個(gè)滿二叉樹(shù)中的編號(hào)就是2m和2m+x?1之間，即第x個(gè)元素就是2m+x?1，訪問(wèn)起來(lái)很方便。
2.3 區(qū)間查詢——單點(diǎn)查詢的升級(jí)版
區(qū)間查詢也不難，規(guī)律同上，這里就直接上代碼。
int query(int s,int t)
{ int ans=-1; for(s+=bit-1,t+=bit+1;s^t^1;s>>=1,t>>=1)
{ if(~s&1)
ans=max(ans,d[s^1]); if(t&1)
ans=max(ans,d[t^1]);
} return ans;
}
2.4 區(qū)間修改——差分思想
區(qū)間修改這時(shí)候看起來(lái)就很難辦了……呃，怎么辦呢？？
經(jīng)過(guò)作者一個(gè)中午的實(shí)驗(yàn)，發(fā)現(xiàn)，用上述代碼的思想似乎較難完成O(log2 n)級(jí)別的區(qū)間修改。這時(shí)候，翻開(kāi)zkw神犇PPT講稿，發(fā)現(xiàn)……原來(lái)，可以用差分的思想。
3、差分思想
差分？
差分是化絕對(duì)為相對(duì)的重要手段。我們接下來(lái)，數(shù)組里的d值就不在存最大值dn了，而是另外開(kāi)個(gè)數(shù)組m，存mn=dn?dn>>1，讓每一個(gè)結(jié)點(diǎn)的值都是存他與他父親結(jié)點(diǎn)的差值。
有什么用嗎？
當(dāng)然有（不然說(shuō)了干什么）！這時(shí)候，我們進(jìn)行區(qū)間修改，就只需要修改mn的值。
這時(shí)候查詢可以完成嗎？可以。
單點(diǎn)查詢就是在m數(shù)組中，從要查的結(jié)點(diǎn)一直查到根結(jié)點(diǎn)，再加上d數(shù)組的值，就可以找到答案（這個(gè)應(yīng)該很好理解吧）。
小插曲
然后，我們?cè)趯?xiě)代碼的時(shí)候會(huì)發(fā)現(xiàn)，如果我們把d數(shù)組初始化為0的話，那么所有的修改都記在數(shù)組m中，d數(shù)組的值會(huì)變嗎？不會(huì)。
因此，我們干脆連值也不存了，把差分的“標(biāo)記”直接當(dāng)作值。于是，基本的差分思想就出來(lái)了。
不過(guò)，值得一提的是，在常數(shù)上，差分的寫(xiě)法可能更大一些（不一定會(huì)明顯優(yōu)于遞歸版的普通線段樹(shù)）。
3.1 差分思想與建樹(shù)
這時(shí)候，每個(gè)點(diǎn)就像前面說(shuō)的，存差就好了。代碼如下，應(yīng)該很好理解：
void build(int n)
{ for(bit=1;bit<=n+1;bit<<=1); for(int i=bit+1;i<=bit+n;i++)
scanf("%d",&d[i]); for(int i=bit-1;i;i--)
{
d[i]=min(d[i<<1],d[i<<1|1]);
d[i<<1]-=d[i];d[i<<1|1]-=d[i];
}
}
3.2 差分思想與單點(diǎn)修改
你當(dāng)然可以嘗試區(qū)間修改，然后用像 query(1,1,x) 這樣的方法修改。
不過(guò)完全沒(méi)有這個(gè)必要。
void update(int s,int t,int x)
{ int tmp; for(d[s]+=x;s>1;s>>=1)
{
tmp=max(d[s],d[s^1]);d[s]-=tmp;d[s^1]-=tmp;d[s>>1]+=tmp;
s>>=1;
}
}
3.3差分思想與單點(diǎn)查詢
不得不承認(rèn)，差分思想的運(yùn)用，唯一一個(gè)不好的地方就是單點(diǎn)查詢從O(1)變?yōu)榱薕(log2 n)，但是他可以幫助我們完成區(qū)間修改的操作，因此也只好忍受一下了。
因?yàn)椴罘执鎯?chǔ)方式的運(yùn)用，相應(yīng)的，這時(shí)候的代碼就成了這樣：
void query(int x)
{
int res=0; while(x)
res+=d[x],x>>=1; return res;
}
3.4差分思想與區(qū)間修改
就為了這個(gè)區(qū)間查詢，我們幾乎把內(nèi)容翻了一倍——講差分存儲(chǔ)方式。而這種方式就是能夠讓我們完成區(qū)間修改。修改方式在上面介紹差分作用時(shí)提過(guò)了，這里就不在贅述了。代碼：
void update(int s,int t,int x)
{ int tmp; for(s+=bit-1,t+=bit+1;s^t^1;s>>=1,t>>=1)
{ if(~s&1)
d[s^1]=x; if(t&1)
d[t^1]=x;
tmp=min(d[s],d[s^1]);d[s]-=tmp;d[s^1]-=tmp;d[s>>1]+=tmp;
tmp=min(d[t],d[t^1]);d[t]-=tmp;d[t^1]-=tmp;d[t>>1]+=tmp;
} while(s>1)
{
tmp=min(d[s],d[s^1]);d[s]-=tmp;d[s^1]-=tmp;d[s>>=1]+=tmp;
}
}
3.5差分思想與區(qū)間查詢
區(qū)間查詢？其實(shí)和之前沒(méi)用差分的差不多，只是把它求出來(lái)之后，再把值依層還原回去。
int query(int s,int t)
{ int lans=-1,rans=-1,ans=-1; for(s+=bit-1,t+=bit+1;s^1^1;s>>=1,t>>=1)
{
lans+=d[s];rans+=d[t]; if(~s&1)
lans=max(lans,d[s^1]); if(t&1)
rans=max(rans,d[t^1]);
} for(ans=max(lans,rans);s>1;)
ans+=d[s>>=1]; return ans;
}
至此，zkw線段樹(shù)的基本操作到這里就講完了。讓我們回顧一下，zkw線段樹(shù)的優(yōu)點(diǎn)不僅在于常數(shù)小，空間小（對(duì)于一般情況下的寫(xiě)法），而且好寫(xiě)好調(diào)，是一種優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)。它的本質(zhì)是非遞歸式線段樹(shù)。希望這篇博客的內(nèi)容對(duì)大家有幫助，滿意請(qǐng)?jiān)谟蚁路近c(diǎn)個(gè)贊，謝謝。
http://www.cnblogs.com/frankchenfu/p/7132445.html
延伸閱讀
- 友誼之樹(shù)上將垂下豐碩的果實(shí) 2022-07-13
- 沉舟側(cè)畔千帆過(guò)，病樹(shù)前頭萬(wàn)木春 】 2022-07-13
- 友誼之樹(shù)上將垂下豐碩的果實(shí) 2022-02-07
- 沉舟側(cè)畔千帆過(guò)，病樹(shù)前頭萬(wàn)木春 2022-02-07
- 種一棵樹(shù)，最好的時(shí)間是十年前，其次是現(xiàn)在 2019-12-05
- 崔博士 2018-08-09
- 淺談在萬(wàn)碼的收獲——任*野 2018-01-25
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來(lái)看看(二) 2017-07-26
- EF查詢百萬(wàn)級(jí)數(shù)據(jù)的性能測(cè)試--單表查詢 2017-07-26
- net.sz.framework 框架 ORM 消消樂(lè)超過(guò)億條數(shù)據(jù)排行榜分析 天王蓋地虎 序言 2017-07-26
友誼之樹(shù)上將垂下豐碩的果實(shí)