ITERATIVE method instead of RECURSIVE one to solve SPOJ GSS1 question

help
, , ,
1

I’m trying to solve the spoj GSS1 using an iterative implementation of segment trees instead of a recursive approach.
I have successfully built the segment tree but I’m finding it difficult to code the query() method using an iterative approach! Can anyone help in implementing the code using an iterative approach?
Link to my code

2

Check out this tutorial on Codeforces for iterative segment trees. For GSS1, the part titled “Non-commutative combiner functions” will be applicable. Since you have already solved it recursively, it shouldn’t be too hard to follow.

2 Likes
3

I have read the tutorial but I’m unable to code the combine() function as described in “Non-commutative combiner functions” section for my use-case.

4

The combine() function should be the same as in your recursive approach. If you didn’t use a separate function to combine nodes, you can just take the procedure of combining two nodes and put that in a separate combine() function.

5

I have implemented it but it gives wrong answer…

6

That’s because you are not combining it correctly. Really it’s much easier to work when you have a separate combine() function. But if you insist on doing without one, the left part should be replaced by something like

left_mps = max(left_mps, left_sum + tree.max_prefix_sum);
left_mss = max(left_mss + tree.sum, tree.max_suffix_sum);
left_max = max(left_max, max(tree.max_sum, left_mss + tree.max_prefix_sum));
left_sum += tree.sum;

Similarly you can work out for right.

7

I would still recommend using a combine() function like

ST combine(ST lt, ST rt) {
    ST x;
    x.max_sum = max(max(lt.max_sum, rt.max_sum), lt.max_suffix_sum + rt.max_prefix_sum));
    x.max_prefix_sum = max(lt.max_prefix_sum, lt.sum + rt.max_prefix_sum);
    x.max_suffix_sum = max(lt.max_suffix_sum + rt.sum, rt.max_suffix_sum);
    x.sum = lt.sum + rt.sum;
    return x;
}
8

Actually the order of calculating sum, max_prefix_sum, max_suffix_sum, max_sum for left and right nodes is tricky!

Your hints and drawing proper diagram helped…

Working code notepad.pw / dushyant7917-GSS1 | The napkin of the internet.

Thanks for help :slight_smile:

9

Nice work :slight_smile: