For full credit, you need to process a million such queries $($and n is at least

a few hundred thousand$),$ this is not feasible.

There is actually a $\backslash$Theta $($log n$)$ algorithm for answering range queries in AVL

trees. But for this algorithm, you will need to store subtree sizes at every node.

In other words, at every node, you need to store the number of descendants of

that node. Once you have subtree sizes, range queries can be answered more

quickly. I won$$t give the full solution, but let me give some hints.

As I always say, think recursion. Suppose you want to find the size of a range

$[$str$1,$ str$2]$ in the subtree rooted at some node, say x$.$ First, compare the key at x with str$1$ and str$2.$ You will have three possibilities for the comparisons

$($assuming$,$ of course, that str$1<$ str$2).$ Two of the those possibilities can be

resolved by a single recursive call.

The third case is the interesting one, where you have to look at both children

of x$.$ But, if you think about it carefully, for the child subtrees, you only need

to answer a $$less than$$ or $$greater than$$ query. These are queries where you

need to find the number of nodes greater than $($or less than$)$ a given string.

These types of queries can again be handled by recursion. Here, you will

notice $($again thinking about it carefully$)$ that if subtree sizes are already stored,

then it will save you recursive calls. Indeed, $$less than$$ or $$greater than$$ queries

can be answered by making at most one recursive call.