Map Sum Pairs

medium trie design

Problem

insert(key, val) and sum(prefix) returns the sum of all values whose keys start with prefix.

Inputinsert('apple',3); sum('ap'); insert('app',2); sum('ap')

Output3 then 5

Cumulative prefix sums.

input

class MapSum:
    def __init__(self): self.root = {}; self.vals = {}
    def insert(self, key, val):
        delta = val - self.vals.get(key, 0); self.vals[key] = val
        node = self.root
        for c in key: node = node.setdefault(c, {}); node['#'] = node.get('#', 0) + delta
    def sum(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node: return 0
            node = node[c]
        return node.get('#', 0)

class MapSum {
  constructor() { this.root = {}; this.vals = new Map(); }
  insert(key, val) {
    const delta = val - (this.vals.get(key) || 0); this.vals.set(key, val);
    let node = this.root;
    for (const c of key) { node = node[c] ||= {}; node['#'] = (node['#'] || 0) + delta; }
  }
  sum(prefix) {
    let node = this.root;
    for (const c of prefix) { if (!node[c]) return 0; node = node[c]; }
    return node['#'] || 0;
  }
}

class MapSum {
    Map vals = new HashMap<>();
    Map sums = new HashMap<>();
    public void insert(String key, int val) {
        int delta = val - vals.getOrDefault(key, 0); vals.put(key, val);
        for (int i = 1; i <= key.length(); i++) sums.merge(key.substring(0, i), delta, Integer::sum);
    }
    public int sum(String prefix) { return sums.getOrDefault(prefix, 0); }
}

class MapSum {
    unordered_map vals, sums;
public:
    void insert(string key, int val) {
        int delta = val - vals[key]; vals[key] = val;
        for (int i = 1; i <= (int)key.size(); i++) sums[key.substr(0, i)] += delta;
    }
    int sum(string prefix) { return sums[prefix]; }
};

Explanation

We need sum(prefix) to instantly total the values of all keys starting with that prefix. The idea is to store, at every node of a trie, the running sum of values for all keys that pass through it. A query then just walks to the prefix node and reads its stored total.

The subtle part is re-inserting an existing key. If apple already has value 3 and we set it to 10, we should not add 10 again — we should add the difference. So we compute delta = val - old_value (tracked in a separate vals map) and push that delta along the path.

During insert we walk each character of the key and add delta to that node's stored sum ('#'). Because the delta flows through every prefix node of the key, all relevant prefix sums stay correct.

Example: insert('apple', 3) adds 3 to a, ap, …, apple, so sum('ap') is 3. Then insert('app', 2) adds 2 along a, ap, app, making sum('ap') equal to 5.

Both operations just walk the key once, so each costs O(L) for a key of length L.

Time: O(L) Space: O(N·L)