## Map Sum Pairs

• Time:Constructor: O(1), insert(key: str, val: int): O(|\texttt{key}|), sum(prefix: str): O(|\texttt{prefix}|)
• Space:O(|\texttt{insert(key: str, val: int)})

## C++

``````struct TrieNode {
vector<TrieNode*> children;
int sum = 0;
TrieNode() : children(26) {}
~TrieNode() {
for (TrieNode* child : children)
delete child;
}
};

class MapSum {
public:
void insert(string key, int val) {
const int diff = val - keyToVal[key];
TrieNode* node = &root;
for (const char c : key) {
if (!node->children[c - 'a'])
node->children[c - 'a'] = new TrieNode;
node = node->children[c - 'a'];
node->sum += diff;
}
keyToVal[key] = val;
}

int sum(string prefix) {
TrieNode* node = &root;
for (const char c : prefix) {
if (!node->children[c - 'a'])
return 0;
node = node->children[c - 'a'];
}
return node->sum;
}

private:
TrieNode root;
unordered_map<string, int> keyToVal;
};
``````

## JAVA

``````class TrieNode {
public TrieNode[] children = new TrieNode[26];
public int sum = 0;
}

class MapSum {
public void insert(String key, int val) {
final int diff = val - keyToVal.getOrDefault(key, 0);
TrieNode node = root;
for (final char c : key.toCharArray()) {
if (node.children[c - 'a'] == null)
node.children[c - 'a'] = new TrieNode();
node = node.children[c - 'a'];
node.sum += diff;
}
keyToVal.put(key, val);
}

public int sum(String prefix) {
TrieNode node = root;
for (final char c : prefix.toCharArray()) {
if (node.children[c - 'a'] == null)
return 0;
node = node.children[c - 'a'];
}
return node.sum;
}

private TrieNode root = new TrieNode();
private Map<String, Integer> keyToVal = new HashMap<>();
}
``````

## Python

``````class TrieNode:
def __init__(self):
self.children: Dict[str, TrieNode] = defaultdict(TrieNode)
self.sum = 0

class MapSum:
def __init__(self):
self.root = TrieNode()
self.keyToVal = {}

def insert(self, key: str, val: int) -> None:
diff = val - self.keyToVal.get(key, 0)
node: TrieNode = self.root
for c in key:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.sum += diff
self.keyToVal[key] = val

def sum(self, prefix: str) -> int:
node: TrieNode = self.root
for c in prefix:
if c not in node.children:
return 0
node = node.children[c]
return node.sum
``````