[HZOI] 山海经 题解

0.题目大意
给出一个序列，每次查询一个区间的最大子段和的端点和值。序列长度 /(n /le 10^{5}/) 。
1.思路
显然应该使用线段树。题目要求每次求一个区间的最大子段和，那么在线段树节点中应该维护这个节点的最大子段和。然而，只维护最大子段和是无法从子节点合并出父节点的。
考虑一个节点，它的最大子段和可能有以下几个来源：

|_____________________________| <-节点 |_________| <-最大子段和 |_______________ |_____________| <-左右子节点 |_____________________________| <-节点 |_________| <-最大子段和 |______

[HZOI] 山海经 题解最先出现在Python成神之路。