題目描述： 設計一個資料結構，支援查詢：給定子陣列 [left, right] 和閾值 threshold，判斷是否存在一個元素在該子陣列中出現次數 >= threshold。如果存在，返回該元素；否則返回 -1。保證如果存在答案，該元素出現次數 > (right - left + 1) / 2。
解題思路：
時間複雜度：建構 O(n)；每次查詢 O(30 * log n)，其中 log n 為二分搜尋
空間複雜度：O(n) — 存儲每個值的位置列表
1. Preprocessing:
a. For each value, store sorted list of its positions
2. Query(left, right, threshold):
a. Repeat 30 times:
- Randomly pick an index in [left, right]
- Get the candidate value at that index
- Binary search to count occurrences in [left, right]
- If count >= threshold: return candidate
b. Return -1 (no majority element found)線段樹 + Boyer-Moore Voting：線段樹的每個節點存儲該區間的候選多數元素。查詢時合併區間候選，再用二分搜尋驗證出現次數。建構 O(n)，查詢 O(log^2 n)。空間 O(n)。確定性算法，無隨機性。
分塊算法（Sqrt Decomposition）：將陣列分成 sqrt(n) 大小的塊。預處理每個塊的頻率。查詢時合併涉及的塊來找候選答案。時間複雜度 O(sqrt(n)) per query。