Suggest structure for query $sumRange(low,high)$ which returns sum of elements whose key $k$ satisfies $low \le k \le high$ in $\Theta(\log n)$ time
Prefix sums or a 1-D summed area table suffice to answer those queries in $O(1)$ time.  (Alternatively, you can augment a balanced binary search tree -- I will let you discover how.)