關(guān)于線段樹

給你一個數(shù)列A，要支持兩個操作：

1.第x個數(shù)加v

2.求x到y(tǒng)這個區(qū)間的和

不要用樹狀數(shù)組做，用線段樹。

線段樹比樹狀數(shù)組看起來美觀一點，它長這樣。

?

它有兩種存儲方式：

1.動態(tài)存儲，使用指針，struct

2.靜態(tài)存儲，直接用數(shù)組，下表遵循左兒子乘2，右兒子乘2加1的規(guī)則。

特別提醒：用Cena評測的時候，不要使用動態(tài)存儲，它分兩種：

1.提前全new出來，一種是一個new一個，它的寫法也分內(nèi)存池和現(xiàn)new。

構(gòu)造：

?

update：

?

?

?

點修改：

?

區(qū)間查詢：

?

區(qū)間修改：

date[now]記錄的是已經(jīng)對當(dāng)前點做過的，但是還沒有對當(dāng)前點的兒子做過的操作。

在每一次修改/查詢之前，調(diào)用pushdown(now,l,r,mid)函數(shù)，下放標記

?

模擬一下過程

區(qū)間修改：

關(guān)于打標機要注意，明確delta含義，不要忘記pushdown

總結(jié)：線段樹最重要的兩個過程是：pushdown和update

線段樹的一個隱藏的重要過程——change和pushdow時都要進行修改。

所有修改函數(shù)，最后都要update，所有函數(shù)，開始都要pushdown。

關(guān)于例題，codevs，洛谷啊什么的都有模板題。

大家可以去做一下。

問一句離騷別愁。

轉(zhuǎn)載于:https://www.cnblogs.com/GTBD/p/9295991.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。