2080. Range Frequency Queries

Range Frequency Queries

題目描述： 給定一個整數陣列 arr，實作一個資料結構，支援查詢：在子陣列 arr[left..right] 中，值 value 出現了幾次。

解題思路： 使用 hash map + 二分搜尋。

1. 預處理：建立一個 map，key 為值，value 為該值出現的所有索引位置（已按升序排列）。
2. 查詢 query(left, right, value)：
   • 取出 value 對應的索引列表。
   • 用 lower_bound 找到 >= left 的第一個位置。
   • 用 upper_bound 找到 > right 的第一個位置。
   • 兩者之差即為 [left, right] 範圍內 value 出現的次數。

這利用了索引列表已排序的特性，二分搜尋在 O(log n) 時間內完成查詢。

時間複雜度：建構子 O(n)，每次查詢 O(log n) — 二分搜尋索引列表。

空間複雜度：O(n) — 儲存所有元素的索引位置。

1. 線段樹 + 離散化：對每個區間節點維護一個值到頻率的映射。可以支援區間修改，但查詢和建構都較複雜，空間 O(n log n)。

2. 分塊（Sqrt Decomposition）：將陣列分成大小 √n 的塊，每塊維護值頻率的映射。查詢時兩端部分暴力、中間整塊查表。建構 O(n)，查詢 O(√n)，介於暴力和二分搜尋之間。

1. 若陣列支援動態更新（修改某個位置的值），如何維護索引列表的正確性？
2. 若查詢改為「在 [left, right] 中出現次數最多的值」，需要什麼不同的資料結構？
3. 如何擴展以支援「在 [left, right] 中出現次數恰好為 k 的值有幾個」？