Map Sum Pairs

Implement MapSum class: insert(key, val) inserts key with value, sum(prefix) returns sum of all values with keys starting with prefix.

Example 1

insert("apple",3), sum("ap")→3, insert("app",2), sum("ap")→5

Solution Approach

Trie where each node stores the sum of values for all words passing through it. On insert, update sums along the path.

TrieNode stores val (exact insert value) and sum (prefix sum).
On insert: traverse/create nodes, at each node update sum by (newVal - oldVal for this key).
On sum(prefix): traverse to end of prefix, return node.sum.

Java

import java.util.*;

class MapSum {
    Map<String,Integer> map = new HashMap<>();
    TrieNode root = new TrieNode();

    public void insert(String key, int val) {
        int diff = val - map.getOrDefault(key, 0);
        map.put(key, val);
        TrieNode node = root;
        for (char c : key.toCharArray()) {
            if (node.ch[c-'a']==null) node.ch[c-'a'] = new TrieNode();
            node = node.ch[c-'a'];
            node.sum += diff;
        }
    }
    public int sum(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (node.ch[c-'a']==null) return 0;
            node = node.ch[c-'a'];
        }
        return node.sum;
    }
    static class TrieNode { TrieNode[] ch=new TrieNode[26]; int sum; }
}

Time Complexity: insert: O(L), sum: O(L)
Space Complexity: O(N*L)