Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
GSS1 segment tree node
struct SegmentTreeNode {
int prefixMaxSum, suffixMaxSum, maxSum, sum;
void assignLeaf(int value) {
prefixMaxSum = suffixMaxSum = maxSum = sum = value;
}
void merge(SegmentTreeNode& left, SegmentTreeNode& right) {
sum = left.sum + right.sum;
prefixMaxSum = max(left.prefixMaxSum, left.sum + right.prefixMaxSum);
suffixMaxSum = max(right.suffixMaxSum, right.sum + left.suffixMaxSum);
maxSum = max(prefixMaxSum, max(suffixMaxSum, max(left.maxSum, max(right.maxSum, left.suffixMaxSum + right.prefixMaxSum))));
}
int getValue() {
return maxSum;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment