前置知識

創(chuàng)新互聯(lián)公司2013年成立，先為策勒等服務建站，策勒等地企業(yè)，進行企業(yè)商務咨詢服務。為策勒企業(yè)網站制作PC+手機+微官網三網同步一站式服務解決您的所有建站問題。

二叉樹

定義

基本操作復雜度： $ O(logn) $

線段樹是一棵二叉樹，每個節(jié)點表示序列上的一段區(qū)間，其中根節(jié)點表示區(qū)間[1,n]。

從根節(jié)點開始，只要區(qū)間長度不為1，就將區(qū)間劃分為兩半，并分給兩個子節(jié)點。

若當前節(jié)點表示區(qū)間[l,r]，

當l≠r時，左孩子表示[l,(l+r)/2]，右孩子表示[(l+r)/2+1,r]；

當l=r時，該節(jié)點為葉子節(jié)點。

基本性質

性質1

線段樹的總節(jié)點數(shù)為2n-1。

性質2

線段樹的層數(shù)約為 $ log_{ 2 } n $ ，即每個葉節(jié)點到根節(jié)點的距離約為 \(log_{2}n\) 。

性質3

任何區(qū)間都可以用不超過 \(2log_{2}n\) 個節(jié)點組合而成。

編號

線段樹的編號方式通常有兩種：即2i和2i+1作i的孩子或按構建順序編號。

存儲

線段樹的存儲也有兩種方式：多個數(shù)組或struct結構體。

以struct結構體數(shù)組為例:

（lc,rc分別為左右孩子的編號，sum為該區(qū)間的總和。

數(shù)組大小為序列長度兩倍。

至于區(qū)間的左右端點[l,r]，可以存儲，也可以遞歸時計算。

若需要節(jié)省空間，則不存儲。）

構建

構建過程遞歸實現(xiàn)，

void build(int u,int l,int r)

（u為當前節(jié)點編號，l,r為區(qū)間端點）

從根節(jié)點開始構建，遞歸時計算并代入l,r，若l=r，該點為葉子節(jié)點，令sum=序列原值，否則，遞歸構建左右孩子，之后令sum=sum左孩子+sum右孩子。

在主程序中：

t=1;

build(1,1,n);

即可。

應用

單點修改

修改過程遞歸實現(xiàn)，

void update(int u,int l,int r,int x,int w)

（u當前節(jié)點編號,l和r為區(qū)間端點，x為要修改的位置，w為變化量）

從根節(jié)點開始修改，若當前點為葉子節(jié)點，使sum+=w并返回
否則判斷x在左孩子還是右孩子，遞歸進行修改，之后令sum=左孩子sum+右孩子sum。

在主程序中調用：

update(1,1,n,x,y);

區(qū)間和查詢

查詢過程遞歸實現(xiàn)，

void query(int u,int l,int r,int ll,int rr)

（u為當前節(jié)點，l和r是區(qū)間端點，ll和rr分別為所查詢區(qū)間的左右端點）

需要用外層定義變量ans儲存答案。

從根節(jié)點開始，首先判斷查詢區(qū)間與節(jié)點區(qū)間是否完全重合，若重合，ans+=sum并返回，否則判斷查詢區(qū)間是否完全在左孩子或者右孩子，若是則遞歸查詢。否則將查詢區(qū)間拆分，兩側分別遞歸查詢。

在主程序中：

ans=0;

query(1,1,n,x,y);

維護區(qū)間最大值/最小值

區(qū)間修改

我們在線段樹的每個節(jié)點上再儲存一個信息，稱為“標記”，記為tag，表示該節(jié)點所包含的每個位置，都要再加上tag。

首先，像區(qū)間詢問一樣將區(qū)間對應到盡量少的節(jié)點上，

令它們

	sum+=(r-l+1)*w;//增加的區(qū)間和
	tag+=w;//增加標記 

然后將sum信息向上pushup。

區(qū)間修改后的單點/區(qū)間查詢

查詢與之前類似，

查詢過程遞歸實現(xiàn)，

void query(int u,int l,int r,int ll,int rr,int w)

但由于標記的出現(xiàn)，多了“下傳標記”一步。

下傳標記時，孩子的標記要疊加。

類似于pushup，標記下傳的過程寫入一個

void pushdown(int u,int l,int r)

注

一個節(jié)點上的tag一定已經計入自身的sum。

在修改和查詢時，只要需要進入子節(jié)點，就一定要pushdown。

注意

當維護信息較多時，為簡化代碼，通常將類似于”a[u].sum=a[a[u].lc].sum+a[a[u].rc].sum”的上傳信息的步驟寫入void pushup(int u)并調用pushup(u);

并非原創(chuàng)，僅是整理，請見諒