在競程圈一直流傳著一個奇怪的傳說:「任何題目都可以使用線段樹來解決」。
他不算是什麼宗教啦,但如果你能熟練利用線段樹這個資料結構的話,那說明你已經不是一個程式競賽的初學者了,你一定有在演算法跟資料結構上面下很大的功夫。
還有一點時間,我們試著快速的把線段樹介紹一下吧!
通常來說,線段樹可以拿來解決多次詢問「l~r區間的最大值、最小值、總合、相乘」。
以8格的陣列來舉例。
首先建立一個16格的二元樹,然後把目前陣列的內容存到葉子上。
接著開始運算出葉子的上一層,把0-1、2-3、4-5、6-7 的答案存進去。
再算出更上一層也就是 0-3、4-7,然後最後一層是0-7。
(上面寫的是存哪個區間的答案,左閉右閉)
所以我們的樹會長這個樣子:
詢問的時候也就很簡單了,比如今天問0-3,就直接dfs下去找到03的位置直接回傳檔案。
如果今天要求的是2-4,那就是可以dfs得到23的答案跟4的答案,再現場去運算出來。
這期是超快速、超粗淺的介紹線段樹,實際上線段樹還有很多東西可以討論,如果有產生興趣的話,歡迎還是上網看看其他人的教學喔!