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