antivenom's blog

Help needed in GSS1 :)
By antivenom, history, 10 years ago, In English

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

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

Comments Comments (4)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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.

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

      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

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

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

→ Reply