GATE 2014 CS (CS3) – Question 49
A balanced BST T holds n numbers. To sum the m numbers between given L and H, the tightest upper bound is $O(n^a\log^bn+m^c\log^dn)$. Find $a+10b+100c+1000d$.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 110 to 110
Explanation
Search to the range boundary inO(logn), then traverse the mqualifying nodes in sorted order while pruning subtrees outside the range. TotalO(logn+m)=O(n⁰log¹n+m¹log⁰n). Thus **a+10b+100c+1000d=110**. No subtree-sum augmentation is specified.