線段樹是所有數據結構中,最常用的之一。線段樹的功能多樣,既可以代替樹狀數組完成“區(qū)間和”查詢,也可以完成一些所謂“動態(tài)RMQ”(可修改的區(qū)間最值問題)的操作。其中,它們大部分都是由遞歸實現的,因此就有一些問題——棧空間占用大和常數大。
因此,從中便衍生了一種非遞歸式的線段樹(作者是THU的張昆瑋,參見他自己的PPT講稿《統(tǒng)計的力量-線段樹》),命名為zkw線段樹。
以下內容均用zkw線段樹保存區(qū)間最大值作為演示。
線段樹是所有數據結構中,最常用的之一。線段樹的功能多樣,既可以代替樹狀數組完成“區(qū)間和”查詢,也可以完成一些所謂“動態(tài)RMQ”(可修改的區(qū)間最值問題)的操作。其中,它們大部分都是由遞歸實現的,因此就有一些問題——棧空間占用大和常數大。
因此,從中便衍生了一種非遞歸式的線段樹(作者是THU的張昆瑋,參見他自己的PPT講稿《統(tǒng)計的力量-線段樹》),命名為zkw線段樹。
以下內容均用zkw線段樹保存區(qū)間最大值作為演示。