947. Prefix Counts That Change

Run q operations against a MULTISET of words, so the same word may be stored several times.

add w store one more copy of w del w remove one copy of w; the problem guarantees a copy is stored count p print how many stored copies begin with the string p

``` add apple, add apply, count app, del apple, count app, count appl -> 2, 1, 1

add ab, add ab, count ab, del ab, count ab -> 2, 1

add cat, count dog, count c -> 0, 1 ```

The second line is the point of the word MULTISET. Two copies of ab count as two, and one delete leaves one.

## What a rebuild costs

The obvious version keeps a list and answers count p by testing every stored word. With 10000 stored words and 10000 counting queries that is 10^8 word tests of up to 20 characters, so 2 * 10^9 character comparisons. Rebuilding a fresh trie before each query is worse.

## One integer per node, and it is already the answer

Give each node a counter cnt. Inserting a word walks it and increments the counter at every node it lands on. Deleting walks the same path and decrements.

Then cnt[v] is exactly how many stored copies pass THROUGH v, and a copy passes through v exactly when the prefix v stands for is a prefix of it. So the answer to count p is cnt at the node p leads to, read with no work at all.

add w: node = root; for each letter: create if missing; step; cnt[node] += 1 del w: node = root; for each letter: step; cnt[node] -= 1 count p: walk p; if a letter has no child print 0, else print cnt[node]

## Why the counter is right even when words are prefixes of each other

cnt[v] counts insertions that walked over v, and an insertion of w walks over exactly the nodes of the non-empty prefixes of w. So a word that is itself a prefix of another is counted at every node they share, which is what the question asks for: a, ab and abc all begin with a, and the node for a holds 3.

## The two places it goes wrong

Do NOT increment the root. The root is the empty prefix and no query ever asks for it, and incrementing it costs nothing but invites the off-by-one where the count at depth 1 is read from depth 0.

A count for a prefix that fell off the trie must print 0. The trap is code that breaks out of the walk and then prints cnt[node] for wherever it stopped: on a trie holding only cat, the query catx breaks at x and would print the count stored at cat, which is 1 rather than 0.

## Nodes are not removed here

A deleted word leaves its nodes in place with a counter of 0, which is harmless because a count of 0 is the right answer for them. Problem 946 is the version where the nodes must actually go, and it needs a different argument to decide which ones.

## Against problem 936

936 builds the trie once from a fixed word list and then answers prefix counts. Here the multiset changes while the queries run, which is why the counter has to support subtraction as well as addition.

## Cost

Every operation costs the length of its word, at most 20 steps, so the whole stream is at most 20000 * 20 = 400000 steps. Counts are at most 20000 and nothing here overflows.

Constraints - `1 ≤ q ≤ 20000` - Every `w` and every `p` is 1 to 20 lowercase English letters. - A `del w` is only given when at least one copy of `w` is currently stored. - The same word may be added several times, and each copy counts separately.