maximaxi's blog

How are Segment Trees used in Competitions?
By maximaxi, history, 9 years ago, In English

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.

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Did you see this?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not yet; you (and the author) have been very helpful, thanks!

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by maximaxi (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

This post has a good implementation of segment trees.

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

http://a2oj.com/Category.jsp?ID=25

Lots of problems related to segtrees.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Awesome, time to get to practice. :) You rock

    → Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Just in time, I would say. http://codeforces.me/blog/entry/20592 :)

→ Reply