Range query in persistent trie

help
1

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.

2

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 :slight_smile: