Help in understanding segment tree merge function of SPOJ FREQUENT question

help
, , ,
1

Can someone please explain the merge function(line 33 to 49) in below code. Why line 48 and 49 always holds true in all the cases!

Code Link

1 Like
2

i am unable to understand the what values u are storing in this varible

struct Tree{

ll mf; // max frequency

ll mpf; // max prefix frequency

ll msf; // max suffix frequency

ll mpn; // max prefix number

ll msn; // max suffix number
};

3

I think its clear what hes storing. Where did you get stuck gyan? If you arent familiar with struct, its allows you to make a custom data type.

1 Like
4

No need to store 5 values at a node. you can do it by storing only 3 values. Link

2 Likes
5

reason of making this variable and what does the necessity.
merge function in this programme is little compicated in this code.
need help @vijju123. yep i am familiar with struct.

6

i didn’t get the logic in ur code @divik544

7

@vijju123 @divik544 Whats the logic behind using left(prefix) and right(suffix) part to find the max frequency in current node?

8

if u read the problem carefully it is mentioned that the input will be sorted so at any node in a segment tree we store 3 values. Added comments for clarity LINK

1 Like
9

Now it became clear… thanks for adding comments in the code

1 Like