segment tree range minimum query

Question

I am trying to understand segment trees. This is a great tutorial that shows how to find a minimum in range. However, it is said there that "All levels of the constructed segment tree will be completely filled except the last level. Also, the tree will be a Full Binary Tree because we always divide segments in two halves at every level.". I do not understand how adding is performed? For example, if we add two more elements 6 and 10 - where should they go? Into the right subtree? If yes, there will be 5 not very balanced and halves are not equal. Should I somehow reorder the tree and do computations again?

kraskevich · Accepted Answer · 2014-10-01 18:35:40Z

1

This implementation of a segment tree does not support add operation, so it is not possible to add a new element.

answered Oct 1, 2014 at 18:35

kraskevich

18.6k4 gold badges37 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Bob Over a year ago

Can you give an example what implementation support add operation?

kraskevich Over a year ago

You can use balanced binary search tree to store segment tree's nodes to make adding new elements possible.

Bob Over a year ago

But when balancing you will have to recompute distances, which is not very efficient.

kraskevich Over a year ago

Recomputation is required only for those nodes that are rotated or are on the path from the root to a new leaf. There are only O(log N) such nodes.

Collectives™ on Stack Overflow

segment tree range minimum query

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related