# 677. Map Sum Pairs 键值映射

@TOC

## # 题目描述

Implement a MapSum class with insert, and sum methods.

For the method insert, you'll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.

For the method sum, you'll be given a string representing the prefix, and you need to return the sum of all the pairs' value whose key starts with the prefix.

Example 1:

``````Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5
``````

## # 解题方法

### # 字典

``````class MapSum {
public:
/** Initialize your data structure here. */
MapSum() {

}

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

int sum(string prefix) {
int count = 0;
const int N = prefix.size();
for (auto a : m_) {
if (a.first.substr(0, N) == prefix) {
count += a.second;
}
}
return count;
}
private:
unordered_map<string, int> m_;
};

/**
* 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:
/** Initialize your data structure here. */
MapSum() {

}

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

int sum(string prefix) {
int res = 0, n = prefix.size();
for (auto it = m_.lower_bound(prefix); it != m_.end(); ++it) {
if (it->first.substr(0, n) != prefix) break;
res += it->second;
}
return res;
}
private:
map<string, int> m_;
};

/**
* 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 Node(object):
def __init__(self, count = 0):
self.children = collections.defaultdict(Node)
self.count = count

class MapSum(object):

def __init__(self):
"""
"""
self.root = Node()
self.keys = {}

def insert(self, key, val):
"""
:type key: str
:type val: int
:rtype: void
"""
curr = self.root
delta = val - self.keys.get(key, 0)
# 更新保存键值对的keys
self.keys[key] = val

curr = self.root
# 更新节点的count
curr.count += delta
for char in key:
curr = curr.children[char]
curr.count += delta

def sum(self, prefix):
"""
:type prefix: str
:rtype: int
"""
curr = self.root
for char in prefix:
if char not in curr.children:
return 0
curr = curr.children[char]
return curr.count

# Your MapSum object will be instantiated and called as such:
# obj = MapSum()
# obj.insert(key,val)
# param_2 = obj.sum(prefix)
``````

C++版本的前缀树实现如下，注意需要手写析构函数。

``````class MapSum {
public:
/** Initialize your data structure here. */
MapSum() {}

void insert(string key, int val) {
int inc = val - vals_[key];
Trie* p = &root;
for (const char c : key) {
if (!p->children[c])
p->children[c] = new Trie();
p->children[c]->sum += inc;
p = p->children[c];
}
vals_[key] = val;
}

int sum(string prefix) {
Trie* p = &root;
for (const char c : prefix) {
if (!p->children[c])
return 0;
p = p->children[c];
}
return p->sum;
}
private:
struct Trie {
Trie():children(128, nullptr), sum(0){}
~Trie(){
for (auto child : children)
if (child) delete child;
children.clear();
}
vector<Trie*> children;
int sum;
};

Trie root;
unordered_map<string, int> vals_;
};

/**
* Your MapSum object will be instantiated and called as such:
* MapSum obj = new MapSum();
* obj.insert(key,val);
* int param_2 = obj.sum(prefix);
*/
``````