Implement MapSum class: insert(key, val) inserts key with value, sum(prefix) returns sum of all values with keys starting with prefix.
insert("apple",3), sum("ap")→3, insert("app",2), sum("ap")→5
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.
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)