Design a map that allows you to do the following:


	Maps a string key to a given value.
	Returns the sum of the values that have a key with a prefix equal to a given string.


Implement the MapSum class:


	MapSum() Initializes the MapSum object.
	void insert(String key, int val) Inserts the key-val pair into the map. If the key already existed, the original key-value pair will be overridden to the new one.
	int sum(string prefix) Returns the sum of all the pairs' value whose key starts with the prefix.


&nbsp;
Example 1:

Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]

Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)


&nbsp;
Constraints:


	1 &lt;= key.length, prefix.length &lt;= 50
	key and prefix consist of only lowercase English letters.
	1 &lt;= val &lt;= 1000
	At most 50 calls will be made to insert and sum.


	class MapSum:

		def __init__(self):
			self.cache = {}

		def insert(self, key: str, val: int) -> None:
			self.cache[key] = val

		def sum(self, prefix: str) -> int:
			len_prefix = len(prefix)
			total = 0
			for word, value in self.cache.items():
				if word[: len_prefix] == prefix:
					total += value

			return total
class MapSum {
    private Map<String, Integer> map;
    private Map<String, Integer> words;

    public MapSum() {
        this.map = new HashMap<>();
        this.words = new HashMap<>();
    }
    
    public void insert(String key, int val) {
        Integer lookup = this.words.getOrDefault(key, null);
        int diff;
        if (lookup == null)
            diff = val;
        else
            diff = val - lookup;
        
        int k = key.length();
        
        StringBuilder sb = new StringBuilder(); 
        for (int i = 0; i < k; i++) {
            sb.append(key.charAt(i));
            
            String prefix = sb.toString();
            map.put(prefix, map.getOrDefault(prefix, 0) + diff);
        }
        
        this.words.put(key, val);
    }
    
    public int sum(String prefix) {
        return this.map.getOrDefault(prefix, 0);
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */
class MapSum {
public:
    map<string,int>mp;
    MapSum() {

    }

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

    int sum(string prefix) {
        int count=0;
        for(auto i:mp){
            int j;
            for(j=0;j<i.first.size() && j<prefix.size();j++){
                if(i.first[j]!=prefix[j])break;
            }
            if(j==prefix.size())count+=i.second;
        }
        return count;
    }
};
var MapSum = function() {
    this.hashKeys = new Map();
    this.hashVals = new Map();
};

MapSum.prototype.insert = function(key, val) {
    let prefix = '';
    for (const str of key) {
        prefix += str;
        const hashKey = this.hashKeys.get(prefix) ?? new Set();
        hashKey.add(key);
        !this.hashKeys.has(prefix) && this.hashKeys.set(prefix, hashKey);
    }
    this.hashVals.set(key, val);
};

MapSum.prototype.sum = function(prefix) {
    const hashKey = this.hashKeys.get(prefix);
    if (!hashKey) return 0;
    let sum = 0;
    hashKey.forEach(key => sum += this.hashVals.get(key));
    return sum;
};
Map Sum Pairs