Last active
December 10, 2015 05:08
-
-
Save utkarshl/4385331 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| struct node | |
| { | |
| int segmentSum,bestPrefix,bestSuffix,bestSum; | |
| node split(node& l, node& r){} | |
| node merge(node& l, node& r) | |
| { | |
| segmentSum = l.segmentSum + r.segmentSum; | |
| bestPrefix = max( l.segmentSum + r.bestPrefix , l.bestPrefix ); | |
| bestSuffix = max( r.segmentSum + l.bestSuffix , r.bestSuffix ); | |
| bestSum = max( max( l.bestSum , r.bestSum) , l.bestSuffix + r.bestPrefix ); | |
| } | |
| }; | |
| node createLeaf(int val)//the leaf nodes, which represent a single element of the array, will be created in this manner | |
| { | |
| node n; | |
| n.segmentSum = n.bestPrefix = n.bestSuffix = n.bestSum = val; | |
| return n; | |
| } | |
| //range_query and update function remain same as that for last problem |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
what's the use of segmentSum,bestPrefix,bestSuffix,bestSum variables can you please elaborate with an example ?