題目描述：

請你設(shè)計一個數(shù)據(jù)結(jié)構(gòu)，它能求出給定子數(shù)組內(nèi)一個給定值的?頻率?。

子數(shù)組中一個值的?頻率?指的是這個子數(shù)組中這個值的出現(xiàn)次數(shù)。

請你實現(xiàn)?RangeFreqQuery?類：

• RangeFreqQuery(int[] arr)?用下標(biāo)從?0?開始的整數(shù)數(shù)組?arr?構(gòu)造一個類的實例。
• int query(int left, int right, int value)?返回子數(shù)組?arr[left...right]?中?value?的?頻率?。

一個?子數(shù)組?指的是數(shù)組中一段連續(xù)的元素。arr[left...right]?指的是?nums?中包含下標(biāo)?left?和?right?在內(nèi)?的中間一段連續(xù)元素。?

?代碼思路：

類初始化?__init__?方法

1. 輸入?yún)?shù)：接收一個整數(shù)列表?arr。
2. 數(shù)據(jù)結(jié)構(gòu)：使用?defaultdict(list)?來存儲每個值在數(shù)組?arr?中出現(xiàn)的所有索引。defaultdict?是 Python?collections?模塊中的一個容器，它允許我們通過默認(rèn)工廠函數(shù)（這里是?list）來自動初始化缺失的鍵。
3. 填充字典：遍歷數(shù)組?arr，對于每個元素?v?和其索引?i，將索引?i?添加到字典?dct?中鍵?v?對應(yīng)的列表中。這樣，dct[value]?將會是一個列表，包含所有值為?value?的元素的索引。

查詢方法?query

1. 輸入?yún)?shù)：接收三個整數(shù)?left、right?和?value，分別表示查詢的左邊界、右邊界和要查詢的值。
2. 查詢邏輯：
   • 使用?bisect.bisect_left?函數(shù)在?dct[value]?列表中查找第一個大于或等于?left?的索引的位置。這個位置之前的所有索引都不在查詢區(qū)間?[left, right]?內(nèi)。
   • 使用?bisect.bisect_right?函數(shù)在?dct[value]?列表中查找第一個大于?right?的索引的位置。這個位置之前的所有索引（不包括這個位置本身）都在查詢區(qū)間?[left, right]?內(nèi)。
   • 計算這兩個位置之間的差值，即?bisect_right?返回的位置減去?bisect_left?返回的位置。這個差值就是值?value?在區(qū)間?[left, right]?內(nèi)出現(xiàn)的次數(shù)。

代碼實現(xiàn)：

class RangeFreqQuery:def __init__(self, arr: List[int]):self.dct = defaultdict(list)for i, v in enumerate(arr): self.dct[v].append(i)def query(self, left: int, right: int, value: int) -> int:return bisect.bisect_right(self.dct[value], right) - bisect.bisect_left(self.dct[value], left)