Map Sum Pairs — Trie with Value Propagation

Problem

Implement:

insert(key, val) — insert key-value pair
sum(prefix) — return sum of all values whose keys start with prefix

Solutions

Python

class MapSum:
    def __init__(self):
        self.root={}; self.vals={}
    def insert(self, key: str, val: int) -> None:
        diff=val-self.vals.get(key,0); self.vals[key]=val
        node=self.root
        for c in key:
            if c not in node: node[c]={'_sum':0}
            node=node[c]; node['_sum']+=diff
    def sum(self, prefix: str) -> int:
        node=self.root
        for c in prefix:
            if c not in node: return 0
            node=node[c]
        return node['_sum']

Complexity

Time: O(L) per operation | Space: O(n * L)