        self.table = {}


    def insert(self, key: 'str', val: 'int') -> 'None':
        diff = val - self.table.get(key, 0)
        if diff != 0:
            self.table[key] = val
            node = self.root
            for c in key:
                node = node.next[c]
                node.sum += diff
