主題
題目連結：
題目意譯：
請設計一個資料結構可以找到給定子陣列中的給定數值之頻率。
一個子陣列中的一個數值之頻率為該數值於該子陣列中之出現次數。
實作類別 RangeFreqQuery：
RangeFreqQuery(int[] arr) 建構一個此類別之實例，其有著給定之索引值從 0 開始的陣列 arr。
int query(int left, int right, int value) 回傳子陣列 arr[left...right] 中 value 的頻率。
一個子陣列為一陣列中的連續元素之序列。 arr[left...right] 代表的是包含索引值位於 left（含）到 right（含）之間的元素之子陣列。
限制：
1 ≦ arr.length ≦ 10 ^ 5
1 ≦ arr[i], value ≦ 10 ^ 4
0 ≦ left ≦ right < arr.length
最多呼叫 query 10 ^ 5 次。
範例測資：
範例 1：
輸入
["RangeFreqQuery", "query", "query"]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
輸出
[null, 1, 2]
解釋
RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]);
rangeFreqQuery.query(1, 2, 4); // 回傳 1。在子陣列 [33, 4] 中，數字 4 出現 1 次。
rangeFreqQuery.query(0, 11, 33); // 回傳 2。在整個陣列中，數字 33 出現 2 次。
解題思維：
先把 arr 中每個數字與其原始的索引值綁在一起，然後根據數字大小排序；大小一樣再排索引值。
接著對於每一次的 query(left, right, value)，我們便可以利用二分搜尋法（Binary Search）去找 value 有沒有在 arr 中。如果有的話出現位置在不超出 [left, right] 範圍中最左邊（索引值盡可能小）L、最右邊 R 是哪裡。此時 L 、 R 於排序後的陣列中所在的位置之差值即為所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
