應(yīng)用情況
線段樹非常通用沪饺，是基于分治思想的二叉樹怜姿。區(qū)間查詢問題一般都可以試試（一般沒有沒有單點(diǎn)查詢的），有單點(diǎn)修改和區(qū)間修改砌创。有些問題甚至可以離散化轉(zhuǎn)換成區(qū)間問題虏缸。（待驗(yàn)證。）
值域線段樹的重要誤區(qū)
值域線段樹以值本身作為下標(biāo)嫩实，值的出現(xiàn)次數(shù)存在線段樹里刽辙。值域線段樹和普通的線段樹的區(qū)別只是用例的使用方式的區(qū)別，而根據(jù)這種不同的應(yīng)用方式才把這類線段樹分類叫做值域線段樹而已甲献。因此線段樹的內(nèi)部實(shí)現(xiàn)絲毫不受影響扫倡。因此在開發(fā)值域線段樹時(shí)一定封裝，不受用例的使用方式的干擾竟纳，而時(shí)刻注意線段樹提供的接口撵溃。
接口設(shè)計(jì)
- 添加和刪除往往可以合并，只是正負(fù)的問題
- 詢問全局的答案也就是詢問root節(jié)點(diǎn)的答案
內(nèi)部實(shí)現(xiàn)的總設(shè)計(jì)思路
既然是分治思想的線段樹锥累，查什么缘挑，保存什么（通常），再存一下分治合并時(shí)需要的信息即可桶略。區(qū)間被完全覆蓋的優(yōu)化是時(shí)間復(fù)雜度的保證语淘，因此思考查詢與修改時(shí)區(qū)間被完全覆蓋滓侍、和非完全覆蓋合并時(shí)的兩種情況如果更新广鳍，當(dāng)然也可以考慮子節(jié)點(diǎn)（優(yōu)先考慮葉節(jié)點(diǎn)）如何更新父節(jié)點(diǎn)。一定記住葉節(jié)點(diǎn)一定被完全覆蓋膝蜈。實(shí)現(xiàn)時(shí)一定銘記向下遞歸一定是有選擇性的操作 鹅心。
綜上：
- 查什么吕粗，保存什么。思考葉節(jié)點(diǎn)儲(chǔ)存的信息
- 思考父節(jié)點(diǎn)如何由子節(jié)點(diǎn)更新而來(lái)旭愧，考慮額外的維護(hù)信息
- 考慮修改查詢操作的完全覆蓋和非完全覆蓋（深知葉節(jié)點(diǎn)一定被覆蓋）
具體實(shí)現(xiàn)
- 建樹颅筋。常常我們會(huì)對(duì)一個(gè)區(qū)間建樹宙暇。
//這是掃描線的代碼
void build(int u, int e, int o)
{
l[u]=e; r[u]=o; //左右端點(diǎn)賦值
if(e==o-1) return; //判葉節(jié)點(diǎn)
umid; //向下遞歸
build(ul, e, mid);
build(ur, mid, r);
}
- 區(qū)間操作：判斷操作區(qū)間與當(dāng)前節(jié)點(diǎn)區(qū)間的包含關(guān)系：完全覆蓋，非完全覆蓋（傳標(biāo)記议泵，左右選擇遞歸占贫，合并更新）
//這是掃描線的代碼
void modi(int u, int e, int o, int d)
{
//既然是分治的線段樹結(jié)構(gòu) ，查什么先口，保存什么型奥。
//區(qū)間被完全覆蓋的優(yōu)化是時(shí)間復(fù)雜度的保證。
//一定是有選擇性的操作
if(e<=l[u]&&r[u]<=o) times[u]+=d; //被覆蓋
else //沒被覆蓋碉京，討論下遞歸
{
umid;
if(e<=mid) modi(ul, e, mid, d);
if(o>mid) modi(ur, mid, r, d);
}
//合并更新
if(times[u]) width[u] = raw[r[u]] - raw[l[u]];
else width[u] = width[ul] + width[ur];
}
//這是區(qū)間求和的板子厢汹，
int query(int p, int e, int o)
{
if(e<=l[p]&&r[p]<=o) //先判斷完全覆蓋
return sum[p];
//非完全覆蓋
spread(p); //有標(biāo)記時(shí)先下傳，選擇性的合并
pmid;
int ans = 0;
if(e<=mid) ans+= query(pl, e, o);
if(o>mid) ans+= query(pr,e,o);
return ans;
}
- 單點(diǎn)修改：葉節(jié)點(diǎn)直接修改更新收夸，其他節(jié)點(diǎn)選一邊遞歸下去再合并更新。
各種不同維護(hù)信息的例題模板
- 區(qū)間乘加血崭，區(qū)間求和
- 區(qū)間并
- 求區(qū)間最值
下面還有亟待解決的更難問題卧惜，也代表了即將學(xué)習(xí)平衡樹和樹套樹。
曾老的OJ上有許多例題夹纫。
靈活多變的線段樹
實(shí)際上線段樹非常靈活：可以維護(hù)離散的序列舰讹，也可以維護(hù)真正的一維幾何區(qū)間（例如掃描線）茅姜。
空間限制
可以動(dòng)態(tài)開點(diǎn)和線段樹合并，勢(shì)能分析可得總體復(fù)雜度是線性對(duì)數(shù)的月匣。
也可以離散化（貌似就不能在線了）钻洒。
正在更新
帶著走還是儲(chǔ)存邊界？
如果沒有初值锄开，那就懶得建樹素标，那我就直接帶著走算了
