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 的值有幾個」?