線段樹
這篇文章就是線段樹模闆和各類用法（懶标記，掃描線，可持久化，樹套樹）的大雜燴。個人不用樹狀數組是以不談。
樸素的線段樹模闆
宏定義：
#define mid ((l+r)>>1)
#define Lson root<<1,l,mid
#define Rson root<<1|1,mid+1,r
建立線段樹
void build(int root,int l,int r)//目前節點編号，左區間，右區間
{
if (l==r)//遞歸到了葉子節點
{
sum[root]=a[i];//葉子節點的内容因我們
//維護的内容而異
return ;
}
build(Lson);
build(Rson);
pushup(root);
}
pushup操作将我們計算出來的左子樹和右子樹的結論更新到根節點中。更新操作也是因我們要維護的區間内容而異。
這裡的代碼維護了一個區間和。
void pushup(int root)
{
sum[root]=sum[root<<1]+sum[root<<1 | 1];//左右兒子節點和
}
單點修改操作：
void change(int root,int l,int r,int x,int v)//x點權值修改成v
{
if (l==r)//目标位置
{
sum[root]=v;//修改操作
return ;
}
if (x<=mid)//左兒子上
change(Lson,x,v);
else//右兒子身上
change(Rson,x,v);
pushup(root);
}
區間查詢操作：
int Query_sum(int root,int l,int r,int ql,int qr)//目前節點是rt,目前區間[l,r],目标區間[ql,qr]
{
int ans=0;
if (ql<=l && r<=qr) //目标區間包括了目前區間[l,r]
return sum[root];//直接傳回目前區間
if (ql<=mid) //目标區間有部分在目前區間的左邊
ans+=Query_sum(Lson,ql,qr);
if (qr>mid)//目标區間有部分在目前區間的右邊
ans+=Query_sum(Rson,ql,qr);
Push_up(root);
return ans;
}
區間修改與線段樹懶标記
懶标記的實質：推遲資訊更新
這邊以最小值的區間修改為例
隻要是update和query操作，都需要加入pushdown
在update中的pushdown并不能做到底，找到update的所有區間就停止了，是以query中還需要pushdown一次保證每個查詢區間覆寫的值都加上了懶标記的效果。
如果一道題目包含加減乘除等各種操作，pushdown的時候還要記錄是哪種操作延遲進行。
struct TreeNode
{
int val;
int mark;//延遲标記
}Tree[1e5+10];//定義線段樹
void build(int root,int l, int r)
{
Tree[root].mark = 0;//----設定标延遲記域
if(l == r)//葉子節點
segTree[root].val = arr[istart];
else
{
build(LSon);//遞歸構造左子樹
build(RSon);//遞歸構造右子樹
//根據左右子樹根節點的值，更新目前根節點的值
Tree[root].val = min(Tree[root<<1|1].val, segTree[root<<1].val);
}
}
void pushDown(int root)
{
if(Tree[root].mark != 0)
{
//設定左右孩子節點的标志域，因為孩子節點可能被多次延遲标記又沒有向下傳遞
//是以是 “+=”
Tree[root<<1|1].mark += Tree[root].mark;
Tree[root<<1].mark += Tree[root].mark;
//根據标志域設定孩子節點的值。因為我們是求區間最小值，是以當區間内每個元
//素加上一個值時，區間的最小值也加上這個值
Tree[root<<1|1].val += Tree[root].mark;
Tree[root<<1].val += Tree[root].mark;
//傳遞後，目前節點标記域清空
Tree[root].mark = 0;
}
}
int query(int root, int l, int r, int ql, int qr)
{
//查詢區間和目前節點區間沒有交集
if(ql > l || qr > r)
return 0x3f3f3f3f3f3f3f;//因為求的是最小值，如果沒有交集自然不用計入
//最小值，于是用inf代替
//目前節點區間包含在查詢區間内
if(ql <= l && qr >= r)
return Tree[root].val;
//分别從左右子樹查詢，傳回兩者查詢結果的較小值
pushDown(root); //延遲标志域向下傳遞
//這個時候就是我們要查詢傳回值的時候了，必須pushdown更新
return min(query(LSon, ql, qr),
query(RSon, ql, qr));
}
void update(int root, int l, int r, int ul, int ur, int addVal)
{
//分多少類和query是一樣的
//更新區間和目前節點區間沒有交集
if(ul > l || ur > r)
return ;
//目前節點區間包含在更新區間内
if(ul <= l && ur >= r)
{
Tree[root].mark += addVal;
Tree[root].val += addVal;
return ;
}
pushDown(root); //延遲标記向下傳遞
//更新左右孩子節點
update(LSon, ul, ur, addVal);
update(RSon, ul, ur, addVal);
//根據左右子樹的值回溯更新目前節點的值
Tree[root].val = min(Tree[root<<1|1].val, Tree[root<<1].val);
}
解題中重要的問題
- 怎麼判斷能否用線段樹？隻要通過左右區間的屬性能得到整個區間的屬性就行。（操作為：修改+（不一定是區間，整體1到n也可以的）查詢）
- 線段樹應該存儲哪些屬性？結果不可直接求出的話，求要求的結果需要用到什麼屬性就存什麼。
主席樹
補充習題部分
Crane
- 向量是可以疊加的
- 維護目前區間從頭指向尾的向量v。一開始初始化為每一段的長度即可。
-
還要維護左子樹到右子樹轉了多少角度w
通過v和w就可以用左右子樹的向量解出整個區間的向量了，最後查詢1到n。
再讀《挑戰程式設計競賽》——出類拔萃（3） pushup的時候先把左子樹的向量旋轉y角再和右子樹的向量相加。
向量的旋轉公式：
再讀《挑戰程式設計競賽》——出類拔萃（3）
冒泡排序的最大次數
這是個求逆序數的問題。逆序數還可以用歸并排序計算。
對于每個j，要求求出i<j且a[j]>a[i]的i的個數。
for(int j=0;j<n;j++)
{
ans+=j-query(1,a[j]);//j-a[j]之前的數的個數
add(a[j],1);//j正式變為“之前的數”
}
Acwing1275 最大數
m個操作，說明最多有m個數。建立有m個數的線段樹，由于求最大值，沒有值的地方初始化為0即可。
如果是A操作，隻要把n+1位置改為添加的數。
懶标記+掃描線 Acwing 247 亞特蘭蒂斯