# ITERATIVE method instead of RECURSIVE one to solve SPOJ GSS1 question

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?

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

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.

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.

I have implemented it but it gives wrong answer…

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

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;
}```

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…