Hello, I'm just getting started with Segment Trees and I'm curious as to what they can be used for in terms of programming competitions. I know the basic RMQ, GCD, and cumulative sum concepts but I'm not sure what else they can be used for, and what types of problems I should look out for to apply segment trees with.
Any applications and/or problem links would be appreciated.
Thanks for this amazing community,
Max
Edit: Thanks for your responses.
Did you see this?
Not yet; you (and the author) have been very helpful, thanks!
I'm also a beginner but i can just share what i have learnt till now.
RMQ,BIT,Cumulative Sum Concept and Sqrt Decomposition data structures are used when there aren't much complex operations.For example find the sum of given range in a array or find the maximum value in a range.Defintely you can also solve them using segment tree as well.
But when you need to apply too many complex operations(like range update) and also need extra variables(or even a built in ds like array/map/vector) to solve the problem then you must use segment tree.For example when you need to find number of distinct elements in a range,find the GCD of all elements in a range or sum/multiplication of elements in a range.And all of them includes range update like(changing value/adding new value/multiplying with new value).
You can check this site for more variations of data structure problems :)
Thank you!
Auto comment: topic has been updated by maximaxi (previous revision, new revision, compare).
This post has a good implementation of segment trees.
Awesome, thanks!
http://a2oj.com/Category.jsp?ID=25
Lots of problems related to segtrees.
Awesome, time to get to practice. :) You rock
Just in time, I would say. http://codeforces.com/blog/entry/20592 :)
Thanks!