GSS1线段树
题目链接:https://www.luogu.com.cn/problem/SP1043
考虑采用分治的思想来维护最大子段和，那么一个大的序列的最大子段和是怎么表示的呢？
想到用区间的左右端点表示这个最大子段和所在的区间，于是我们对这个区间的端点位置进行讨论。
这个图表示所有端点都在左边的区间上的情况，于是把左子区间的最大子段和计入候选值。
这个图表示所有端点都在右边的区间上的情况，于是把右子区间的最大子段和计入候选值。
这个图表示区间左端点在左边，右端点在右边的情况，这个可以拆分成左子区间的最大后缀和加上右子区间的最大前缀和，将这个值计入候选值。
将这三个最大子段和的候选值去\maxmax即得该区间的最大子段和。
为了维护最大子段和，引进了最大前缀和和最大后缀和，所以接下来解决区间的最大前缀和和最大后缀和。
还是使用分治的思想，把要求的区间分成两个子区间，对前缀和的右端点进行讨论。
这个图表示右端点在左边的情况，此时将左区间的最大前缀和计入候选值。
这个图表示右端点在右边的情况，此时可拆分成左子区间和和右子区间的最大前缀和，将这个值计入候选值。
以上两个候选值取\maxmax即得到该区间的最大前缀和，最大后缀和同理。
维护最大前缀和与后缀和是，引入了区间和，而这个是很好完成的。
在查询的时候分类讨论一下，如果这个区间要拆分，那么将两个部分算出来后在合并一下就好了，所以建议大家在这一天写结构体式线段树，返回结构体就好归并啦。
看起来不可做，实际上还好，此题是做过的这种类型的第一题，继续