Loading...
Loading...
Loading...
Farhan keeps the payments of his hostel mess in a binary search tree. A refund is stored as a negative amount. The n amounts are inserted, in the given order, into an empty tree.
The warden asks q questions. Each question gives two amounts L and R. Print the sum of all stored amounts v with L ≤ v ≤ R. Print 0 when no amount is in the range.
Example
Input
7 50 30 70 20 40 60 80 3 35 65 1 10 20 80
Output
150 0 350
40 + 50 + 60 = 150. Nothing lies from 1 to 10. Every amount lies from 20 to 80: the total is 350.
Try the problem first. Open one hint at a time.
If a node is smaller than L, its whole left subtree is smaller too. Only its right subtree can help.
If a node is larger than R, only its left subtree can help.
Otherwise the node counts, and both subtrees may hold more amounts in the range.
Up to 1000 amounts near 10^9 add up to about 10^12. Keep the sum in a long.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor