在競程圈一直流傳著一個奇怪的傳說：「任何題目都可以使用線段樹來解決」。

他不算是什麼宗教啦，但如果你能熟練利用線段樹這個資料結構的話，那說明你已經不是一個程式競賽的初學者了，你一定有在演算法跟資料結構上面下很大的功夫。

還有一點時間，我們試著快速的把線段樹介紹一下吧！

通常來說，線段樹可以拿來解決多次詢問「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的答案，再現場去運算出來。

結語

這期是超快速、超粗淺的介紹線段樹，實際上線段樹還有很多東西可以討論，如果有產生興趣的話，歡迎還是上網看看其他人的教學喔！

本期meme