I am trying to solve problem based on persistent trie. I am unable to understand how to handle range queries in persistent trie. Please provide some help regarding how to process range queries for persistent trie data structure.
Since it is a persistent trie,
There will be n versions of the trie…
the ith version representing the trie of the range from 1 to i.
At each node in every trie, store the count of number of words which end in its subtree.
Now for processing range queries, where the range is from L to R.
take the (L-1)th version and Rth version.
While traversing the trie, in order to know whether the current trie node is in the range L-R,
just check whether:
it exists in the (L-1)th version, and
(count stored in node of Rth version) - (count stored in node of (L-1)th version) > 0
if it doesn’t exist in the (L-1)th version but exists in the Rth version
Hope this helped