Suppose we have a balanced binary search tree $T$ holding $n$ numbers. We are given two numbers $L$ and $H$ and wish to sum up all the numbers in $T$ that lie between $L$ and $H$. Suppose there are $m$ such numbers in $T$. If the tightest upper bound on the time to compute the sum is $O(n^a \log^b n + m^c \log^d n)$, the value of $a + 10b + 100c + 1000d$ is _______.

To find and sum all elements in a balanced Binary Search Tree within the range $[L, H]$:

1. Locating the boundaries: Finding the starting node (the lowest common ancestor or the smallest element $\ge L$) takes $O(\log n)$ time because the height of the balanced BST is $O(\log n)$.

2. Visiting the elements: Once the range is found, traversing and summing the $m$ matching nodes (for example, by an in-order traversal that prunes subtrees outside $[L, H]$) visits $O(\log n + m)$ nodes in total, which takes $O(\log n + m)$ time.

Thus, the tightest upper bound on time complexity is:

Comparing with the expression $O(n^a \log^b n + m^c \log^d n)$:

• $a = 0$

• $b = 1$

• $c = 1$

• $d = 0$

Calculating the required linear combination: