iT邦幫忙

2023 iThome 鐵人賽

DAY 17
0

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

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

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

通常來說,線段樹可以拿來解決多次詢問「l~r區間的最大值、最小值、總合、相乘」。

以8格的陣列來舉例。

首先建立一個16格的二元樹,然後把目前陣列的內容存到葉子上。

接著開始運算出葉子的上一層,把0-1、2-3、4-5、6-7 的答案存進去。

再算出更上一層也就是 0-3、4-7,然後最後一層是0-7。

(上面寫的是存哪個區間的答案,左閉右閉)

所以我們的樹會長這個樣子:

https://ithelp.ithome.com.tw/upload/images/20231001/20133574OuZBdkPLMf.png

詢問的時候也就很簡單了,比如今天問0-3,就直接dfs下去找到03的位置直接回傳檔案。

如果今天要求的是2-4,那就是可以dfs得到23的答案跟4的答案,再現場去運算出來。

結語

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

本期meme

https://ithelp.ithome.com.tw/upload/images/20231001/201335742Q4jJROyLs.jpg


上一篇
Day16 我要當忍者大師
下一篇
Day18 敏捷開發
系列文
寫程式的那些宗教戰爭30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言