解題說明
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 節點何時可以安全地被釋放？