Medium · Trie Aggregate Values
Understand → Visualise → Practice.
Process key-value assignments and prefix-sum queries, returning query results in order.
Each trie node keeps the sum of values of all keys passing through it. A prefix query is then one walk and one read.
Remember each key's current value in a map.
On set key = v, walk the key's path and add v − old value to every node.
Walk the prefix and return its node's total, or 0 if the path doesn't exist.
O(key length) per operation and O(total characters) space.
Adding v instead of the difference double-counts keys that are set again.
Read the full guide first: Tries and Prefix Search.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.