You are not logged in. Please login at www.codechef.com to post your questions!

×

Help in understanding segment tree merge function of SPOJ FREQUENT question

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

asked 23 Mar '18, 17:29

dushyant7917's gravatar image

5★dushyant7917
716
accept rate: 0%

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

(23 Mar '18, 18:38) gyanendra3713★
1

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.

(23 Mar '18, 19:16) vijju123 ♦♦5★
2

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

(23 Mar '18, 20:24) divik5444★

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.

(23 Mar '18, 20:56) gyanendra3713★

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

(23 Mar '18, 21:38) gyanendra3713★

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

(23 Mar '18, 22:17) dushyant79175★
1

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

(24 Mar '18, 08:35) divik5444★
1

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

(24 Mar '18, 10:36) dushyant79175★
showing 5 of 8 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,738
×1,768
×1,137
×10

question asked: 23 Mar '18, 17:29

question was seen: 379 times

last updated: 24 Mar '18, 10:36