线段树——区间最大子段和问题（SPOJ - GSS1）

问题描述：

给定一段长度为$n$的序列$a_1,a_2,\dots ,a_n$（$a$有正亦有负），每次 询问$[L,R]$（即$a_L$~$a_R$）范围内的最大子段和，并涉及 单点修改 操作。

【线段树】 维护区间最大子段和：

①定义：

线段树一共要维护$4$个值，如下：（每个值的含义都是相对于该结点对应区间$[l,r]$而言）

struct node
{
    int sum;       //[l,r]区间之和int max_sum;   //[l,r]内的最大子段和int max_pre;   //[l,r]内的最大前缀和int max_post;  //[l,r]内的最大后缀和
}t[maxn<<2];

②向上传递

以下画棵线段树模拟一下其实挺好理解的。

void pushup(int rt)
{
    int ls=rt<<1,rs=rt<<1|1;t[rt].sum = t[ls].sum+t[rs].sum;//区间之和 = 左区间之和+右区间之和t[rt].max_sum = max(max(t[ls