Блог пользователя suraj021

Beginning 2D Segment trees?
Автор suraj021, 8 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 Bug 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.

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить