题目

类型：design

解题思路

字典树
由于要处理前缀，自然而然联想到可以用 Trie（前缀树）来处理此问题。
在前缀对应的 Trie 的每个节点存储该前缀对应的值。

• insert 操作：首先求出前缀对应的值的改变 delta，直接在 Trie 节点上更新键 key 的每个前缀对应的值。
• sum 操作：直接在前缀树上搜索该给定的前缀对应的值即可，如果给定的前缀不在前缀树中，则返回 0。

当然在实际中也可以在 Trie 的节点只存储键 key 对应的 val, 每次求 sum 时利用 DFS 或者 BFS 遍历前缀树的子树即可。

代码

class MapSum {
    class TrieNode {
        int val = 0;
        TrieNode[] next = new TrieNode[26];
    }
    TrieNode root;
    Map<String, Integer> map;
    public MapSum() {
        root = new TrieNode();
        map = new HashMap<>();
    }
    public void insert(String key, int val) {        
        int delta = val - map.getOrDefault(key, 0);
        map.put(key, val);
        TrieNode node = root;
        for (char c : key.toCharArray()) {
            if (node.next[c - 'a'] == null) {
                node.next[c - 'a'] = new TrieNode();
            }
            node = node.next[c - 'a'];
            node.val += delta;
        }
    }
    public int sum(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (node.next[c - 'a'] == null) {
                return 0;
            }
            node = node.next[c - 'a'];
        }
        return node.val;
    }
}