Map Sum Pairs — Editorial

Opening the reading…

Intuitionwhy every prefix can store its answer directly

A prefix query asks for the values of all keys beginning with the same characters. Those keys form one branch of a trie: after reading the prefix, every matching key continues below the node reached by that prefix. If that node stores the sum of all values passing through it, the query answer is already available without scanning the keys below it.

Insertion has one detail that changes the whole design. Replacing a key does not add its new value to the old total; it changes the contribution by new value minus old value. Store the current value in a separate hash map, compute that difference, and add it to every trie node on the key's path. A new key has old value zero, so the same update handles both cases.

Approachone delta keeps every stored sum synchronized

Create a trie root and a hash map of current key values, because the trie stores aggregate sums but cannot by itself tell you the old value of a key being replaced.

For insert(key, val), read the old value from the hash map or use zero when the key is new, then compute delta = val - old value; without this difference, overwriting a key would count its old contribution twice.

Store val as the key's new value in the hash map, so the next overwrite uses the correct previous contribution.

Walk from the root through every character of key, creating a child node when it does not exist and adding delta to each reached node; every one of those nodes represents a prefix containing this key.

For sum(prefix), walk the trie along the prefix characters, because the node reached after the final character stores exactly the values of keys that share that prefix.

Return zero as soon as a required child is missing, and otherwise return the final node's sum; no key can match a prefix whose trie path does not exist.

Complexitythe key and prefix lengths control the walks

MEASURE	BOUND	WHY
Time	Insert: expected O(L); sum: expected O(P)	Insertion performs one hash-map lookup and one update for each of the L characters, with no trie node visited twice. A sum query examines only its P-character path and stops at the first missing child. The bounds degrade with the input shape to O(L) and O(P) per operation even when the trie has no shared prefixes; the stated expected bound assumes ordinary hash-table behavior.
Space	O(U x L) extra in the worst case	The trie has at most one node for each character position of each stored key, so completely separate paths use O(U x L) nodes; the key-value hash map adds O(U) entries. The returned integer is not stored output, and no output array is involved, so all of this is working memory. Shared prefixes can make the actual trie smaller.

Here L is the inserted key length, P is the queried prefix length, and U is the number of distinct keys stored. Hash-map operations are treated as expected constant time.

Annotated solutionC++ · trie with prefix sums and overwrite deltas

CPPStore a sum at every trie node and update the path by the overwrite delta.

#include <string>
#include <unordered_map>

using namespace std;

class Solution {
private:
    struct TrieNode {
        int sum;
        unordered_map<char, TrieNode*> children;

        TrieNode() : sum(0) {}
    };

    TrieNode* root;
    unordered_map<string, int> values;

public:
    Solution() : root(new TrieNode()) {}

    void insert(string key, int val) {
        int oldValue = values.count(key) ? values[key] : 0;
        int delta = val - oldValue;
        values[key] = val;

        TrieNode* node = root;
        for (char c : key) {
            if (!node->children.count(c)) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
            node->sum += delta;
        }
    }

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

The hash map and trie have separate responsibilities. values answers the question that the trie cannot answer: what did this exact key contribute before the latest insert? The trie then spreads only the change through the key's path. Notice that the root itself does not need an aggregate sum, because the problem asks only for nonempty prefixes and every update begins adding at the first character node.

The direct-scan alternativesimpler state, slower prefix queries

A smaller implementation can store only the current key-value pairs and scan them during sum. For each stored key, test whether prefix is its beginning and add its value when it matches. This is a reasonable choice when the number of operations is tiny and code simplicity matters, but it gives up the trie invariant: every sum query revisits unrelated keys instead of following one prefix path.

CPPA direct map-based version that trades faster insertion for a full scan on every sum.

#include <string>
#include <unordered_map>

using namespace std;

class Solution {
private:
    unordered_map<string, int> values;

public:
    Solution() {}

    void insert(string key, int val) {
        values[key] = val;
    }

    int sum(string prefix) {
        int total = 0;
        for (const auto& entry : values) {
            const string& key = entry.first;
            if (key.size() >= prefix.size() &&
                key.compare(0, prefix.size(), prefix) == 0) {
                total += entry.second;
            }
        }
        return total;
    }
};

This alternative makes insert expected O(1), while sum is O(U x P) in the usual prefix-comparison model, with O(U) extra storage for the map. It is not an asymptotic optimisation; the trie is the better design when sum queries matter. The scan is useful as a clear baseline or when the operation limit is so small that the extra structure is not worth maintaining.