線段樹（Segment Tree）是一個基於分治的資料結構。
通常處理區間，序列中的查詢，更改問題。大體上有單修，單查，區修，區查等操作。但因為其可維護變數的多樣性，所以常在各類題目中遇到。準確說，是各類優化中遇到。
線段樹是個有根二元樹，我們記為 t，其每個節點 t[p] 均儲存著所應該記錄的關鍵資訊（依題目情況而定）。對於每一個區間，我一般不喜歡在結構體裡記錄它的區間端點資訊，一般在函數遞迴中開兩個引數進行處理。
首先我們有這樣一個序列a：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
我們希望對其中下標為 \(i\) 的元素進行修改，並且能夠快速查詢區間 \(l\) 到 \(r\) 中的最大值。
struct node{
int mx;
}tree[MAXN];//記錄每個節點裡的關鍵資訊，這裡記錄了節點區間裡的最大值
void build(int i,int tl,int tr){//遞迴建樹，i表示節點編號，tl，tr表示該節點所含的區間（後同）
if(tl == tr){
tree[i].mx = a[tl];
return;
}
int mid = (tl + tr) / 2;
build(i << 1,tl,mid);//進行遞迴建樹操作，分別建左子樹和右子樹
build((i << 1) + 1,mid + 1,tr);
tree[i].mx = max(tree[i<<1].mx,tree[(i<<1) + 1].mx);//子樹建完後，進行上傳操作，更新該區間tree[i]的最大值（意會一下）
}
void change(int i,int tl,int tr,int pos,int num){//pos為要修改的下標，num為修改後的值
if(tl == tr){//已到達要修改的下標
tree[i].mx = num;
return;
}
int mid = (tl + tr) / 2;
if(pos <= mid){//如果包含在左子樹裡，那麼就在該子樹裡進行遞迴直到到達目標節點
change(i<<1,tl,mid,pos,num);
}
else{//被包含在右子樹裡
change((i<<1) + 1,mid + 1,tr,pos,num);
}
tree[i].mx = max(tree[i<<1].mx,tree[(i<<1) + 1].mx);//修改完值後，自然要更新區間包含這個下標的樹上的節點
}
查詢 \(l\) 到 \(r\) 這一區間裡的最大值。
int query(int i,int tl,int tr,int l,int r){
if(l > r)return -MAXN;//區間越界，返回最小值
if(tl == l && tr == r){
return tree[i].mx;
}
int mid = (tl + tr) / 2;//如果查詢的區間被左右子樹各包含一點，那麼將這個查詢的區間分為落在左子樹裡的區間和落在右子樹裡的區間，對分後的兩個區間所返回的最大值取一次最大值
return max(query(i<<1,tl,mid,l,min(r,mid)),query((i<<1) + 1,mid + 1,tr,max(l,mid + 1),r));
}
單點修改，區間查詢的方法就介紹到這裡了。
如果說單點修改，區間查詢的實現中最重要的就是資料的上傳操作，那麼我覺得區間修改，單點/區間查詢最重要的就是資料的下傳操作。
什麼是下傳操作？我們通過對下面這道題的分析來進行理解。
有一列長度為 \(n\) 的路燈，每一次操作下標 \(l\) 到 \(r\) 的路燈的開關，使得每個路燈的狀態發生改變（亮變滅 \(or\) 滅變亮）。所有燈初始時都是滅的，經過 \(m\) 次操作後，有 \(x\) 次查詢，每一次查詢操作給出 \(l\) \(r\) 兩個下標，查詢 \(l\) 到 \(r\) 中有多少盞路燈是亮著的。
在這道題目中，對於修改操作中的 \(l\) \(r\)，如果我們將這個區間裡面每個路燈的狀態逐一進行改變，時間複雜度肯定是不會令人滿意的。但是我們可以對每個節點設定一個標記 \(sta\)，\(1\) 表示該節點所表示的區間內的所有燈都是亮著的，\(0\) 表示所有燈都是滅的，\(-1\) 表示該區間裡既有滅的，又有亮的。
在這個題裡，因為所有燈初始為滅的，且 \(sta\) 的預設值為 \(0\)，我們就可以取消建樹操作。
void change(int i,int tl,int tr,int l,int r){//所有字母含義均一樣，不同的是，在區修的過程中，我們不必改變l和r的值，我們可以讓我們處理的區間範圍來「適應」修改的區間範圍，建議結合程式碼理解
if(tl > r || tr < l)return;//如果當前節點的區間跟修改區間毫不相交，那麼就沒有遞迴處理的必要了，直接返回，這就是「適應」操作
if(tl >= l && tr <= r){//假如當前節點的區間被完全包含在修改的區間裡面，那麼直接整體修改區間的值並返回，不必繼續遞迴（雖然該節點以下的所有子樹的資訊並沒有得到修改）
tree[i].sta = !tree[i].sta;
return;
}
if(tree[i].sta != -1){
tree[i<<1].sta = tree[(i<<1) + 1].sta = tree[i].sta;//注意，這裡就是資料的下傳操作，因為該區間在修改後就會既有亮的又有滅的，而之前在進行整體操作時並沒有對子樹進行修改，所以在修改前就應該把當前節點的紙更新到左兒子和右兒子上
}
tree[i].sta = -1;
int mid = (tl + tr) / 2;
chaneg(i<<1,tl,mid,l,r);
change((i<<1) + 1,mid + 1,tr,l,r);
}