這題是有點變化的RMQ，複習一下寒假學的線段樹，也可以用Sparse Table來作。
繼續閱讀 →

線段樹求區間總合

這棵線段樹基本上概念跟上次的一樣，只是實作的方式不同，參考看看吧!!!

對線段樹感到陌生? 請參考上一篇 : 線段樹處理RMQ問題

原題 : http://zerojudge.tw/ShowProblem?problemid=a693

我的Code(version 2.0.0) : 繼續閱讀 →

線段樹處理RMQ問題

線段樹是一種二元樹，也是一種資料結構，主要就是利用Divide & Conquer思想，使區間最大/最小值的問題(Range Maximum/Minimum Query)，能夠在O(log2(N))內解決，而原本的從頭跑到尾則是O(N)。

上圖為線段樹的示意圖，最下層存的是數列本身(紅字1那格存第1個數，依此類推)，而上層則用來維護L~R這個區間，可以是L~R的最小值、最大值或總和等。而線段樹的深度，則是由數列的大小決定，如果數列有n個數，那我們必須建造一棵葉子節點樹(也就是最後一層)大於等於n的完滿二元樹，應該不難想。繼續閱讀 →