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

Help needed in GSS1 :)
Автор antivenom, история, 9 лет назад, По-английски

Sorry peoples I don't usually post something like my code giving RTE please fix that but this time I am asking help for this.I have tried segment tree implementation many times but never got sucess.I request if anybody can take a glance at my code and point out what's going bad...My code link

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

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

segment tree needs 4 times the size of the normal array but the memory you took is even less than tree times the size of the normal array i didn't look much but this is definitly a bug

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

    Why does it need 4 times the size? I usually allocate twice the nearest power of 2 for Segment Tree. Formally, if the array has n elements, then I allocate 2x + 1 for the Segment Tree, where x is the minimum integer such that 2x ≥ n.

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

      it actually needs three times the size but i see everyone using 4 * Maxn so i thought that consider this the number of nodes being 2 ^ n + 2 -> 3 * 2 ^ n would be the maximum number thus 3 times the size but all people's segment trees aren't the same so yours can take less

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

Bugs I found: - On line 18 you are missing one case, re-check your logic - On line 41 you forgot to type "return" - Even after correcting line 41, your query function will end up in an infinite recursion, because you may call the function to a non-valid interval [low; high] and in this case your program never stops. Try to handle this case separately

→ Ответить