解題說明
Map Sum Pairs
題目描述:設計一個 MapSum 資料結構,支援以下兩種操作:
insert(key, val):插入鍵值對。若key已存在,則更新其值。sum(prefix):回傳所有以prefix為前綴的鍵所對應值的總和。
解題思路:這題天然適合用 Trie(前綴樹) 來解決。在 Trie 的每個節點儲存「通過此節點的所有鍵的值之和」(sum),以及代表某個完整鍵結尾的 val。
進行 insert(key, val) 時,若 key 已存在舊值 old_val,則差值 delta = val - old_val 需要沿著 key 的路徑更新每個節點的 sum(因為那些節點的前綴和都受到影響)。同時用 HashMap 記錄每個 key 的最新 val,方便計算 delta。
進行 sum(prefix) 時,只需沿著 prefix 的路徑走到終點節點,回傳該節點的 sum 即可——因為 sum 已在插入時預計算好,查詢為 O(L)。
C++ 解法
複雜度分析
時間複雜度:insert 為 O(L),sum 為 O(P),其中 L 為鍵的長度,P 為前綴的長度。兩個操作均只需沿 Trie 路徑走一遍,不需要遍歷子樹。
空間複雜度:O(N × L × 26)——Trie 最壞情況下每個字元都是新節點,共 N 個鍵、每個最長 L 字元,每個節點有 26 個指標。另加 O(N) 的 HashMap 儲存鍵值對映。
虛擬碼
1. Initialize Trie with a root node (sum=0) and an empty HashMap key_map. 2. insert(key, val): a. Compute delta = val - key_map[key] (0 if key is new). b. Update key_map[key] = val. c. Walk the Trie along key, creating nodes as needed. d. At each node along the path, add delta to node.sum. 3. sum(prefix): a. Walk the Trie along prefix. b. If any character is missing, return 0. c. Return the sum stored at the final node.
其他解法
方法一:HashMap 暴力查詢
直接用 unordered_map<string, int> 儲存所有鍵值對。insert 為 O(L),sum 需遍歷所有鍵檢查前綴,時間複雜度 O(N × L)。適合 insert 頻繁、sum 很少呼叫的場景,實作簡單但 sum 效率差。
方法二:Trie 不預存 sum,查詢時 DFS 加總
每個節點只存 val(若是某個 key 的結尾),sum(prefix) 走到前綴末節點後,對整棵子樹做 DFS 累加所有 val。insert O(L),sum O(S)(S 為子樹大小)。當前綴較短但子樹很大時效率較差,但程式碼不需要維護 delta 邏輯,更直觀。
方法三:有序 Map + 二分查找
用 std::map<string, int> 的 lower_bound(prefix) 找到第一個 >= prefix 的鍵,再向後迭代直到前綴不匹配。sum 為 O(K log N + K × L),其中 K 為符合前綴的鍵數。對前綴匹配數量少時有優勢。
延伸思考
- 若
insert操作非常頻繁而sum較少,哪種實作方式(Trie vs HashMap vs 有序 Map)最划算?如何根據操作頻率選擇資料結構? - 若鍵不限於小寫英文字母,例如包含 Unicode 字元,Trie 節點的
children陣列應如何改造以節省記憶體? - 如何在此資料結構上支援
delete(key)操作?刪除時 Trie 節點何時可以安全地被釋放?