線段樹總結

???????? ???????? ——這個周末訓練賽和codeforces，加上自己有點偷懶導致進度嚴重推遲

線段樹，顧名思義是在樹上的線段，通過建樹來維護你需要的操作，基本的操作有：區間求和，區間求最值，區間異或（這個實際上和區間更新差不多，就是加上值這個操作換成了異或），區間覆蓋，掃描線求面積，線段樹求區間連續字段。

下面從最基礎的區間求最值開始：

給你一個長度為n的序列，例如長度為5的序列{9,1,8,5,6},最大值和最小值，當然樸素算法在數據量小的時候是可以的，但是在n的數量級特別大的時候就顯得略加笨重。由此想出一種辦法，將數組里的數構成一棵數。如下圖：

?

這棵樹中葉子保存的是每個下標的數值，兩個葉子的父親，保存的是葉子中最小的那一個，這樣一直到根節點得出數列中最小值。最大值也是一樣。說起來很簡單，接著就是用代碼實現，線段樹是一個二叉樹。數據量大的時候也可能是一個完全二叉樹，用一個sum數組來存儲每個節點的數值，然后遞歸建樹。

void build(int i,int l,int r) {if(l==r){scanf("%d",&sum[i]);return ;}int m=(l+r)/2;build(i*2,l,m);build(i*2+1,m+1,r);pushup(i);//收集子節點的結果 }Pushup()函數是將當前節點向下更新void pushup(int i) {sum[i]=min(sum[i*2],sum[i*2+1]); }

當維護用途不同的時候push函數的用法是不一樣的。下面每種用途的線段樹push函數的寫法都有講解。

然后是更新操作：

void update(int id ,int val,int i,int l,int r) {if(l==r){sum[i]=val;//這里的操作的修改id點的值return;}int m=(l+r)/2;if(id<=m) update(id,val,i*2,l,m);else update(id,val,i*2+1,m+1,r);pushup(i); }

修改，查詢操作都是從根節點開始遍歷，然后當你遍歷到的當前區間，在需要區間之內的時候，就可以進行你需要的操作了。

查詢操作：

查詢的時候，一個區間的最值要不就在左區間，要不就在右區間，要不然就在左加右區間（雖然很像廢話，但是就是這樣的）

int query (int rt,int L,int R,int l,int r) {if(L<=l&&r<=R)return sum[rt];int m=(r+l)>>1;int ret=0;if(L<=m)ret=min(ret,query(rt*2,L,R,l,m)if(R>m)ret=min(ret,query(rt*2+1,L,R,m+1,r);return ret; }

區間求和（單點更新，區間更新）：????????

單點更新：

int sum[N*4]; void pushup(int i) {sum[i]=sum[i*2]+sum[i*2+1]; } void build(int i,int l,int r) {if(l==r){scanf("%d",&sum[i]);return ;}int m=(l+r)/2;build(i*2,l,m);build(i*2+1,m+1,r);pushup(i);//收集子節點的結果 } /* 在當前區間[l,?r]內查詢區間[ql,?qr]間的目標值?? 且能執行這個函數的前提是：[l,r]與[ql,qr]的交集非空?? 其實本函數返回的結果也是?它們交集的目標值?? */ int query(int ql,int qr,int i,int l,int r) {if(ql<=l&&r<=qr) return sum[i];int m=(l+r)/2;int cur=0;if(ql<=m) cur+=query(ql,qr,i*2,l,m);if(m<qr) cur+=query(ql,qr,i*2+1,m+1,r);return cur; } /* update這個函數就有點定制的意味了?? 本題是單點更新，所以是在區間[l,r]內使得第id數的值+val?? 如果是區間更新，可以update的參數需要將id變為ql和qr?? */ void update(int id ,int val,int i,int l,int r) {if(l==r){sum[i]+=val;return;}int m=(l+r)/2;if(id<=m) update(id,val,i*2,l,m);else update(id,val,i*2+1,m+1,r);pushup(i); }

區間更新：

這里要引進一個概念叫：延遲更新。當你想要更新一個區間的時候人進一個數組addv，addv[i]表示以i為節點的樹共同增加了(addv[i])，然后在通過遞歸，順帶更新帶葉子結點。

const int MAXN=100000+100; typedef long long LL; #define lson i*2,l,m #define rson i*2+1,m+1,r LL sum[MAXN*4]; LL addv[MAXN*4]; void PushDown(int i,int num)//這就是延遲操作，更新當前結點的葉子 {if(addv[i]){sum[i*2] +=addv[i]*(num-(num/2));//每個點的需要更新的值乘以的個數sum[i*2+1] +=addv[i]*(num/2);//同上addv[i*2] +=addv[i];//這個區間需要更新的個數addv[i*2+1]+=addv[i];addv[i]=0;} } void PushUp(int i) {sum[i]=sum[i*2]+sum[i*2+1]; } void build(int i,int l,int r) {addv[i]=0;//將延遲操作更改的值需要記錄到addv數組中，現在將它初始化if(l==r){scanf("%I64d",&sum[i]);return ;}int m=(l+r)/2;build(lson);build(rson);PushUp(i); } void update(int ql,int qr,int add,int i,int l,int r) {if(ql<=l&&r<=qr){addv[i]+=add;sum[i] += (LL)add*(r-l+1);return ;}PushDown(i,r-l+1);//向下更新枝葉的值int m=(l+r)/2;if(ql<=m) update(ql,qr,add,lson);if(m<qr) update(ql,qr,add,rson);PushUp(i); } LL query(int ql,int qr,int i,int l,int r) {if(ql<=l&&r<=qr){return sum[i];}PushDown(i,r-l+1);int m=(l+r)/2;LL res=0;if(ql<=m) res+=query(ql,qr,lson);if(m<qr) res+=query(ql,qr,rson);return res; }

?

轉載于:https://www.cnblogs.com/wuwangchuxin0924/p/5971849.html

總結

以上是生活随笔為你收集整理的线段树总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。