0
$\begingroup$

I am implementing a 2-3 tree, where every leaf has a unique key and a value, and I need to write an algorithm which finds the sum of values of the leaves which their key is within a given interval. The time complexity of the function needs to be $O(\log n)$.

I thought about saving for each internal node the sum of the leaves in its subtree, but I don't know how to continue from there.

$\endgroup$
1
$\begingroup$

Storing the sum for internal nodes is a good plan.

For every query you also need to search for the two bounds of the interval, and find the leftmost and rightmost leaf with elements in the interval. (The bounds themselves do not need to be in the tree.) The two search paths will split a a certain node. Continue there. While searching for the leftmost leaf you include all sums to the right.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.