suraj021's blog

By suraj021, 4 years ago, In English,

Hello folks, being a beginner I have no idea how 2D segment tree works, complexity etc. Can anyone provide me tutorials, video lecture or anything about its working and implementation? Thanks

UPD: If you cannot help, please stay away from this post and please do not downvote. Because each time you downvote it, this post becomes less valuable and I and many other beginners may not get a chance to learn. And anyone who is polite enough to help, your welcome.

 
 
 
 
  • Vote: I like it
  • -12
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

http://lmgtfy.com/?q=2D+Segment+tree :D
BTW: it's not this bullshit time now :D go ahead & master the basics before learning something new :) ...
good luck :D

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Oh wow. You are so smart. Don't you think that I have already done that. And after failing to understand from quora, other 2D segment tree blogs in cf, I decided to write a new blog. Instead of sarcasm, why don't you teach me? :D

    Btw thanks.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      i would likd to do that but i don't know anything about it , and i don't want to know :D ...
      sorry .

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

      If your intent is to learn it for competitive programming. I am almost sure that no div2 (A, B, C, D) was about segment trees let alone 2D segment trees. So as dwik said, I recommend to learn and practice the basics. Meaning you should be able to solve on average div2 (A, B, C) during the round with acceptable time (under 1 hour). And after that you can turn into more complex stuff. Moreover, usually segment tree problems do not come as a straight forward application. Rather, they require a lot of figuring out before reducing the problem into a segment tree problem.

      PS: I have never solved a segment tree problem officially and I managed to get to 1900.

      Anyway I learnt segment trees from this. It is in Russian so, I recommend using translate.yandex.com if you do not speak Russian.

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

        But my ratting should not stop me from learning new algorithms. BTW I do know about 1D segment trees but 2D scares me...

        Thanks

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The best source I could find with good info about 2D segment tree is e-maxx.ru site. Is in Russian, so I used Yandex for translation to English. Here is a link: https://translate.yandex.com/translate?dir=&url=http%3A%2F%2Fe-maxx.ru%2Falgo%2Fsegment_tree〈=ru-en&ui=en

Once you can code the data structure, I encourage to try this problem https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2272

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks a lot mate . The google translate screwed that up.