主題
（2022 / 11 / 19 更新排版以及若干敘述文字）
題目連結：
題目大意：
以下有一演算法：
１： 輸入 n
２： 印出 n
３： 如果 n = 1 結束
４： 如果 n 是奇數，則 n＝3 * n + 1
５： 否則 n ＝ n / 2
６： GOTO ２
２： 印出 n
３： 如果 n = 1 結束
４： 如果 n 是奇數，則 n＝3 * n + 1
５： 否則 n ＝ n / 2
６： GOTO ２
此演算法已被證實當 0 < n ≦ 1000000 皆會停止。
藉由輸入 n 到此演算法，我們可以得到一連串的數列（1 作結尾）。而此數列的長度（項數）稱為數字 n 的「Cycle-length」。
例 n = 22 時，數列長為 16，也就是 Cycle-length 為 16。
現給定 i、j（0 < i、j ≦ 1000000）。求介於 i、j 之間（皆包含）的數字所產生最大的 Cycle-length 為何？
解題思維：
先將所有可能出現的數字，也就是1 ～ 1000000 都跑過一次那個演算法。
因為步驟 4 會把 n 乘 3 再加上 1，然而新的數必定為偶數所以可以跳到步驟 5，也就是數列的長度一次會 + 2。
然後把所算出來的結果存在一個陣列裡面。
可是這題跟 C039 有個巨大的差距，也就是在給定 i、j 的詢問時。因為詢問數和詢問區間都非常地大。因此只用一般迴圈去抓最大值一定會超時（要在 2 秒內做完）。
所以，我們這次需要一個特別的資料結構——
線段樹（Segment-Tree）
（原本這邊是按照「演算法筆記」命名為「偽線段樹（Fake Segment-Tree）」。但是上了計算幾何（Computational Geometry）之後，發現這個「偽」已經不太重要了，故將其移除）
做法類似二元搜尋樹（Binary Search Tree），把整體一直二分變成一棵樹，如下圖：
我們在這題要做的，即是把我們 n 的區間（1 ～ 1000000），照上圖作成一棵樹（可以用陣列模擬）。而最下面左端點 = 右端點的區間，即是我們剛剛為相應的 n 求出的 Cycle-length。
然後往上合併，以 (0, 0) 、 (1, 1) 合併成 (0, 1) 為例。因為我們要求的是區間的最大值，於是合併時也要求 (0, 0) 、 (1, 1) 兩個區間哪個區間所存的值最大。然後將較大的值存進 (0, 1) 。
(0, 1) 、 (2, 2) 合併成 (0, 2) 時，也是一樣。求 (0, 1) 、 (2, 2) 哪個區間現在存的值最大，將其存進 (0, 2) 裡。接下來都以此類推。
而查詢時，也是跟創造線段樹的時候一樣去二分。
先判斷現在的區間有沒有包含在欲查詢的區間裡面，有的話直接取這個區間存的最大值跟現有的「最大值」作比對。若此區間的比較大，則現有的「最大值」更新成此區間所存之值；反之，就繼續往下二分。
最後求出的「最大值」即是題目所需。
要看線段樹的實作範例，可參見這裡的中上段（或是參考我放在下面的範例程式碼）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
