rahulpadhy's blog

Segment tree
By rahulpadhy, history, 8 years ago, In English

Hi, I am new to segment trees. I am getting RE for this SPOJ question and I am unable to find out the mistake in my code. So, can you guys please help ?? Here's the link to the question... http://www.spoj.com/problems/GSS1/

And, here's my solution.. http://pastebin.com/dtKe4rx4

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

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

Your logic is wrong.

Take this test:

3
2 -1 2
1
1 3

Your output: 4
Answer: 3

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

    Answer should be 4 because we need to find the maximum possible sum obtained from the elements in the specified indices(2 + 2 = 4)... But my main concern is as to why I am getting RE for this question...

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

      You can't do 2 + 2 because there's a -1 in between. Read the problem statement. They want maximum contiguous subarray sum. I solved it, I know what I'm talking about.

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

      As for the runtime error, check out this test:

      3
2 -1 2
1
3 3

      You're not exiting the query function when your current range is completely outside the query range. You should do something like: 

      if (start > r || end < l)
     return 0;
      → Reply