Yath's blog

How much of the segment trees section should I cover from the edu section?
By Yath, history, 15 months ago, In English

I have almost completed the Part1, should I do the whole part 2 or are there some advanced topics(steps) in there which i should avoid. I want to reach expert and want to be able to do 1400-1800 rating(if any) segment tree problems.

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

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

none,there are few problems in that range( I only know 3 problems). so even if you learn segment tree now you will forget by the time you actually need it( that is post 2000 problems). Just focus on stl data structures until you are a bit comfortable with 1900 problems

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    how can you forget segment tree?

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

      Well I learnt them a year ago when I was a pupil and since then have only used them once in a contest, so I forgot many related tricks to segment tree and have to re solve the same problems again on edu a month ago. My point is learning ST and implementing them are two different things So why not learn them later when you are actually able to reach problem D in a div2 contest rather than now.

      → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        Not necessarily, segment trees make much problems easier to solve, many problems could be solved without segment trees but using them makes the solution much easier. I guess anyone whose rate is +1400 should definitely learn basic operations on segment trees.

        → Reply
»
15 months ago, # |
  Vote: I like it +2 Vote: I do not like it

You should just know how to find min,max,xor,gcd,sum of a range, these will be the only type of problems in your rating range

→ Reply
»
15 months ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

I think learning lazy propagation and part 1 are more than enough to reach expert although they aren't crucial

→ Reply
»
15 months ago, # |
  Vote: I like it +12 Vote: I do not like it

You don't need segment tree to reach expert

→ Reply