Map Sum Pairs: Prefix Sums in a Trie

You need to design a MapSum class that supports two operations. insert(key, val) inserts a string key with an integer value, or updates the value if the key already exists. sum(prefix) returns the sum of all values whose keys start with the given prefix.

This is LeetCode 677: Map Sum Pairs, and it combines two ideas you have likely seen separately: a trie for prefix lookups and a hash map for tracking values. The trick is maintaining running prefix sums at each trie node so that sum() queries are instant rather than requiring a subtree traversal.

Trie with prefix sums and delta updates

The brute force approach would store all key-value pairs in a dictionary and, for each sum() call, iterate over every key to check if it starts with the prefix. That is O(n * m) per query, where n is the number of keys and m is the average key length. It works, but it does not scale.

A trie solves the prefix lookup in O(m) time, where m is the length of the prefix. But a basic trie only tells you whether a prefix exists. To return the sum of values below a prefix, you would need to traverse the entire subtree and add up all end-of-word values. That can still be slow if the subtree is large.

The key insight is to store a running sum at every node in the trie. When you insert a key with value val, you add val to every node along the path from root to the end of the key. Then sum(prefix) simply walks to the prefix node and reads the stored sum. No subtree traversal needed.

The second insight handles updates. When a key that already exists is re-inserted with a new value, you need to undo the old value and apply the new one. You do this with a delta: delta = new_val - old_val. Walk the trie path and add the delta to each node's sum. A separate hash map tracks the current value for each key so you can compute the delta.

The solution

class TrieNode:
    def __init__(self):
        self.children = {}
        self.sum = 0

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

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

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

Walking through an example

Let's trace through the four operations shown in the diagram.

Step 1: insert("apple", 3). The key "apple" is not in the hash map, so delta = 3 - 0 = 3. Walk the trie, creating nodes for a, p, p, l, e. Add 3 to the sum at every node along the path, including the root. The hash map now holds {"apple": 3}.

Step 2: insert("app", 2). The key "app" is new, so delta = 2 - 0 = 2. Walk the existing nodes a, p, p and add 2 to each sum. The root sum goes from 3 to 5. The first "p" node sum goes from 3 to 5. No new nodes are created for a, p, p since they already exist. The hash map is now {"apple": 3, "app": 2}.

Step 3: sum("ap"). Walk the trie following "a" then "p". Arrive at the first "p" node and read its sum: 5. This correctly reflects 3 from "apple" plus 2 from "app". Return 5.

Step 4: insert("app", 5). The key "app" already exists with value 2. Compute delta = 5 - 2 = 3. Walk the path a, p, p and add 3 to each node's sum. The root sum goes from 5 to 8. The nodes below "app" (l, e) are unchanged because the delta only propagates along the inserted key's path. Now sum("ap") returns 8, and sum("app") also returns 8.

Complexity

Here m is the length of the key or prefix. Each insert walks the key once, doing O(1) work per character (dictionary lookup, sum update). Each sum query walks the prefix once. The hash map adds O(1) per insert for the delta lookup. Total space for the trie is O(n * m) in the worst case, where n is the number of distinct keys.

Edge cases

• Updating an existing key with the same value: delta is 0, so all sums stay unchanged. The code handles this naturally.
• Prefix that does not exist in the trie: the sum method hits a missing child and returns 0 immediately.
• Single character keys and prefixes: inserting "a" with value 5 means sum("a") returns 5. Make sure the loop processes even single-character inputs correctly.
• Empty prefix: sum("") would return the root's sum, which is the total of all values. The problem constraints may not require this, but the code handles it since the loop body is skipped and node.sum on root is returned.

The building blocks

1. Trie traversal with node-level aggregation

The core pattern is the standard trie walk, but with an extra piece of data at each node. Instead of just tracking children and end-of-word, each node stores an aggregate (in this case, a sum). You update the aggregate during insertion and read it during queries. This same idea extends to storing counts, min/max values, or any other aggregate you need at each prefix level.

2. Delta updates for efficient re-insertion

When a key is updated, you do not rebuild the trie or recompute sums from scratch. Instead, you compute the difference between the new and old values and propagate just that delta along the path. This keeps updates at O(m) instead of O(n * m). The delta pattern shows up in many data structures, including Fenwick trees (binary indexed trees) and segment trees with lazy propagation.

3. Hash map as a side channel

The trie alone does not know the current value of a specific key. You need the hash map to look up the old value when computing deltas. This "trie plus hash map" combination is common in design problems where the trie handles prefix queries and the hash map handles exact-key lookups. The same dual-structure approach appears in LRU Cache (hash map plus doubly linked list) and other design problems that need two different access patterns.

From understanding to recall

You have read through the Map Sum Pairs solution. You see how the trie stores running sums, how delta updates handle re-insertions, and how the hash map tracks current values. The logic is clean: compute delta, walk the trie, add delta to each node.

But can you write it from scratch in five minutes? The TrieNode with a sum field instead of is_end, the delta computation, the hash map lookup with a default of 0. These are small details that slip under pressure.

Spaced repetition closes that gap. You practice writing the insert method with delta propagation and the sum method with prefix traversal at increasing intervals. After a few reps, you see a prefix-sum design problem and the code flows out without hesitation.

Related posts

• Implement Trie - The foundation for all trie problems. Build insert, search, and startsWith from scratch.
• Replace Words - Another trie problem that walks words through a prefix tree, using early termination to find the shortest matching root.
• Design Add and Search Words - Extends the basic trie with wildcard DFS. Same trie structure, different search logic.