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 asked 18 Nov '17, 17:20

Check out this tutorial on Codeforces for iterative segment trees. For GSS1, the part titled "Noncommutative combiner functions" will be applicable. Since you have already solved it recursively, it shouldn't be too hard to follow. answered 19 Nov '17, 16:38
I have read the tutorial but I'm unable to code the combine() function as described in "Noncommutative combiner functions" section for my usecase.
(20 Nov '17, 00:31)
The
(20 Nov '17, 03:03)
I have implemented it but it gives wrong answer...
(20 Nov '17, 12:47)
That's because you are not combining it correctly. Really it's much easier to work when you have a separate left_mps = max(left_mps, left_sum + tree[left].max_prefix_sum); left_mss = max(left_mss + tree[left].sum, tree[left].max_suffix_sum); left_max = max(left_max, max(tree[left].max_sum, left_mss + tree[left].max_prefix_sum)); left_sum += tree[left].sum;Similarly you can work out for right .
(21 Nov '17, 01:50)
I would still recommend using a 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; }
(21 Nov '17, 01:55)
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 https://notepad.pw/dushyant7917GSS1 Thanks for help :)
(21 Nov '17, 15:11)
Nice work :)
(25 Nov '17, 22:32)
showing 5 of 7
show all
