```
class MapSum {
public:
/** Initialize your data structure here. */
struct Node {
Node* children [26];
int sum = 0;
int val = 0;
Node() {
for (int i = 0; i < 26; i++) {
children[i] = NULL;
}
}
};
Node* root;
MapSum() {
root = new Node();
}
int util(Node* current, string& key, int ind, int val) {
int diff = 0;
if (!current->children[key[ind]-'a'])
current->children[key[ind]-'a'] = new Node();
current = current->children[key[ind]-'a'];
if (ind == key.size()-1) {
diff = val-current->val;
current->val = val;
current->sum += diff;
return diff;
}
diff = util(current, key, ind+1, val);
current->sum += diff;
return diff;
}
void insert(string key, int val) {
Node* current = root;
util(root, key, 0, val);
}
int sum(string prefix) {
Node* current = root;
for (char c : prefix) {
current = current->children[c-'a'];
if (!current) return 0;
}
return current->sum;
}
};
```