Design a data structure that supports the following operations:
Insert a key-value pair:
Each key is a string, and each value is an integer.
If the key already exists, update its value to (overriding the previous value).
Return the prefix sum:
Given a string, prefix, return the total sum of all values associated with keys that start with this prefix.
To accomplish this, implement a class MapSum:
Constructor: Initializes the object.
void insert (String key, int val): Inserts the key-value pair into the data structure. If the key already exists, its value is updated to the new one.
int sum (String prefix): Returns the total sum of values for all keys that begin with the specified prefix.
Constraints:
key.length, prefix.length
Both key and prefix consist of only lowercase English letters.
val
At most 50 calls will be made to insert and sum.
This problem requires mapping string keys to integer values and returning the sum of values of all keys that share a given prefix. The core challenge lies in handling both updates (when an existing key is reinserted with a new value) and prefix queries without always scanning all keys. A naive approach will be to store key-value pairs in a hash map and, for each prefix query, iterate over all keys to compute the sum, but this is computationally expensive when the number of keys grows large.
The optimized solution lies in constructing a trie (prefix tree) that stores cumulative sums along the path of each key. Tries are naturally suited for prefix-based problems, and by augmenting each node with a score field, we can quickly retrieve the total sum for any prefix.
However, simply adding values during insertion creates issues when updating an existing key because the prefix sums would be inflated by double-counting. To overcome this, we maintain an auxiliary hash map that stores the current value for each key. Whenever a key is updated, we calculate the delta (the difference between the new value and the old one) and propagate only this delta through the trie. This ensures that prefix sums remain consistent.
While inserting each key, we walk down the trie, character by character, updating the cumulative sum at each node by the delta. When answering a prefix query, we traverse the trie along the prefix. While traversing, if the path exists, we return the score of the node at the end of the prefix that contains the total sum of all matching keys. Otherwise, we return
Design a data structure that supports the following operations:
Insert a key-value pair:
Each key is a string, and each value is an integer.
If the key already exists, update its value to (overriding the previous value).
Return the prefix sum:
Given a string, prefix, return the total sum of all values associated with keys that start with this prefix.
To accomplish this, implement a class MapSum:
Constructor: Initializes the object.
void insert (String key, int val): Inserts the key-value pair into the data structure. If the key already exists, its value is updated to the new one.
int sum (String prefix): Returns the total sum of values for all keys that begin with the specified prefix.
Constraints:
key.length, prefix.length
Both key and prefix consist of only lowercase English letters.
val
At most 50 calls will be made to insert and sum.
This problem requires mapping string keys to integer values and returning the sum of values of all keys that share a given prefix. The core challenge lies in handling both updates (when an existing key is reinserted with a new value) and prefix queries without always scanning all keys. A naive approach will be to store key-value pairs in a hash map and, for each prefix query, iterate over all keys to compute the sum, but this is computationally expensive when the number of keys grows large.
The optimized solution lies in constructing a trie (prefix tree) that stores cumulative sums along the path of each key. Tries are naturally suited for prefix-based problems, and by augmenting each node with a score field, we can quickly retrieve the total sum for any prefix.
However, simply adding values during insertion creates issues when updating an existing key because the prefix sums would be inflated by double-counting. To overcome this, we maintain an auxiliary hash map that stores the current value for each key. Whenever a key is updated, we calculate the delta (the difference between the new value and the old one) and propagate only this delta through the trie. This ensures that prefix sums remain consistent.
While inserting each key, we walk down the trie, character by character, updating the cumulative sum at each node by the delta. When answering a prefix query, we traverse the trie along the prefix. While traversing, if the path exists, we return the score of the node at the end of the prefix that contains the total sum of all matching keys. Otherwise, we return