Here is a trick that I recently learned: using defaultdict to build Trie with a few lines of code.

COUNT = None
def _trie():
ret = collections.defaultdict(_trie)
ret[COUNT] = 0
return ret
class MapSum(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.key_val = {}
self.root = _trie()
def insert(self, key, val):
"""
:type key: str
:type val: int
:rtype: void
"""
diff = val - self.key_val.get(key, 0)
self.key_val[key] = val
root = self.root
for c in key:
root[COUNT] += diff
root = root[c]
root[COUNT] += diff
def sum(self, prefix):
"""
:type prefix: str
:rtype: int
"""
root = self.root
for c in prefix:
root = root[c]
return root[COUNT]