188. In an AVL tree augmented with subtree sizes, count the keys in [a, b].
MediumTrees
Technical
Show model answer
Define `countLess(x)`, the number of keys strictly less than x: walk down, and whenever the current key is less than x, add its left subtree size plus 1 and go right; otherwise go left. Then the range count is `countLess(b) - countLess(a) + (b is present ? 1 : 0)`, or equivalently count(<= b) - count(< a).
Each walk is one root-to-leaf path, so the query is O(log n) regardless of how many keys are in the range, compared with O(log n + k) for listing them.