MediumRating 1702
2080. Range Frequency Queries
arrayhash-tablebinary-searchdesignsegment-tree
解題說明
Range Frequency Queries
題目描述： 給定一個整數陣列 arr，實作一個資料結構，支援查詢：在子陣列 arr[left..right] 中，值 value 出現了幾次。
解題思路： 使用 hash map + 二分搜尋。
- 預處理：建立一個 map，key 為值，value 為該值出現的所有索引位置（已按升序排列）。
- 查詢 query(left, right, value)：
- 取出 value 對應的索引列表。
- 用 lower_bound 找到 >= left 的第一個位置。
- 用 upper_bound 找到 > right 的第一個位置。
- 兩者之差即為 [left, right] 範圍內 value 出現的次數。
這利用了索引列表已排序的特性，二分搜尋在 O(log n) 時間內完成查詢。
C++ 解法
複雜度分析
時間複雜度：建構子 O(n)，每次查詢 O(log n) — 二分搜尋索引列表。
空間複雜度：O(n) — 儲存所有元素的索引位置。
虛擬碼
1. BUILD: For each index i, append i to positions[arr[i]]. 2. QUERY(left, right, value): a. If value not in positions, return 0. b. In positions[value], binary search for first index >= left → lo. c. Binary search for first index > right → hi. d. Return hi - lo.
其他解法
-
線段樹 + 離散化：對每個區間節點維護一個值到頻率的映射。可以支援區間修改，但查詢和建構都較複雜，空間 O(n log n)。
-
分塊（Sqrt Decomposition）：將陣列分成大小 √n 的塊，每塊維護值頻率的映射。查詢時兩端部分暴力、中間整塊查表。建構 O(n)，查詢 O(√n)，介於暴力和二分搜尋之間。
延伸思考
- 若陣列支援動態更新（修改某個位置的值），如何維護索引列表的正確性？
- 若查詢改為「在 [left, right] 中出現次數最多的值」，需要什麼不同的資料結構？
- 如何擴展以支援「在 [left, right] 中出現次數恰好為 k 的值有幾個」？