线段树——你能回答这些问题吗？(经典应用)

传送门：245. 你能回答这些问题吗 - AcWing题库

思路：

1.在存储的结构体里面加一个sum用于记录当前节点区间的区间和，当前节点p的区间和就是两个子节点的区间和。

t[p].sum=t[p*2].sum+t[2*p+1].sum;

2.再用一个lmax和一个rmax记录当前区间内严格从pl开始的前缀区间和的最大值和严格从pr开始后      缀区间和的最大值。

      当前节点p的lmax取值有以下两种（rmax的情况与左子树的情况类似）：

      一是左子树的lmax

     二是右子树的lmax加上左子树的区间和sum，因为这里lmax要求严格从当前区间的最左边开  始。

t[p].lmax=max(t[2*p].lmax,t[2*p].sum+t[2*p+1].lmax);
    t[p].rmax=max(t[2*p+1].rmax,t[2*p+1].sum+t[2*p].rmax);

3.用一个data记录当前节点所包含的区间的某一段连续区间和的最大值。

想要求出当前节点p的区间[l,r]的某一段连续区间和最大值有三种情况：

一是：左节点2*p的区间和最大值，也就是t[2*p].data

二是：右节点2*p+1的区间和最大值，也就是t[2*p+1].data

三是：lmax+rmax  ,当且仅当lmax和rmax都是非负数。拼接起来刚好是一段连续的区间。

由上述三种情况得到下面的公式

t[p].data=max({t[2*p].data,t[p*2+1].data,t[2*p].rmax+t[2*p+1].lmax});

以上的三个部分都可以在建树和单点修改的过程中递归的进行更新。

------------------------------------------

至于区间内最大连续区间和查询的方法与区间最大值的查询方法类似：

细分为三类情况：

第一种也是最简单的一种：l<=pl<=pr<=r直接返回t[p].data

第二种：pl<=l<=pr<=r ，这种情况下，t[p].data的取值与l 和 mid 的关系有关（mid=(pl+pr)>>1）

当l>=mid+1时可以直接进入右子树就能变成第一种情况。

此时取值的可能只有一种就是右子树节点t[2*p+1].lmax

当l<=mid时则需要递归左子树求出左子树的lmax以及 右子树直接返回值。

此时取值可能有t[2*p].lmax 和t[2*p].sum+t[2*p+1].lmax

l<=pl<=r<=pr的情况和上面类似，省略。

第三种：pl<=l<=r<=pr,这种情况只要两个子树都分别递归进去就能变成第二种情况。

代码：

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e6+10;
int a[N];
struct tree
{
    int l,r;
    int data;
    int sum;
    int lmax;
    int rmax;
}t[N*4];
void bulid (int p,int l,int r)  //线段树建树
{
    t[p].l=l,t[p].r=r;
    if(l==r)
    {
    t[p].data=a[l];
    t[p].sum=a[l];
    t[p].lmax=a[l];
    t[p].rmax=a[l];
    return ;
    }
    int mid=(l+r)/2;
    bulid(2*p,l,mid);
    bulid(2*p+1,mid+1,r);
 
    t[p].sum=t[p*2].sum+t[2*p+1].sum;
    t[p].lmax=max(t[2*p].lmax,t[2*p].sum+t[2*p+1].lmax);
    t[p].rmax=max(t[2*p+1].rmax,t[2*p+1].sum+t[2*p].rmax);
    t[p].data=max({t[2*p].data,t[p*2+1].data,t[2*p].rmax+t[2*p+1].lmax});
}
//单点修改
void change(int p,int x,int v)
{
    if(t[p].l==t[p].r)
    {
    t[p].data=v;
    t[p].sum=v;
    t[p].lmax=v;
    t[p].rmax=v;
    return ;
    }
    int mid =(t[p].l+t[p].r)/2;
    if(x<=mid) change(p*2,x,v);
    else change(2*p+1,x,v);
 
    t[p].sum=t[p*2].sum+t[2*p+1].sum;
    t[p].lmax=max(t[2*p].lmax,t[2*p].sum+t[2*p+1].lmax);
    t[p].rmax=max(t[2*p+1].rmax,t[2*p+1].sum+t[2*p].rmax);
    t[p].data=max({t[2*p].data,t[p*2+1].data,t[2*p].rmax+t[2*p+1].lmax});
}
//区间查询：
tree ask(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r)
        return t[p];
    int mid=(t[p].l+t[p].r)>>1,val=-(1<<30);
    tree a,b,c;
    a.data=a.sum=a.lmax=a.rmax=val;
    b.data=b.sum=b.lmax=b.rmax=val;
    c.sum=0;
    if(l<=mid)
    {
        a=ask(p*2,l,r);
        c.sum+=a.sum;
    }
    if(r>mid)
    {
        b=ask(2*p+1,l,r);
        c.sum+=b.sum;
    }
    c.data=max({a.data,b.data,a.rmax+b.lmax});
    c.lmax=max(a.lmax,b.lmax+a.sum);
    if(l>mid)    //此处的作用是当上面的a没有被更新时是没有返回值的，c的数值会是负无穷，此时需要到右子树获得真正的返回值
        c.lmax=max(c.lmax,b.lmax);
    c.rmax=max(b.rmax,b.sum+a.rmax);
    if(r<=mid)
        c.rmax=max(c.rmax,a.rmax);
 
    return c;
}
 
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    bulid(1,1,n);
    while(m--)
    {
        int k,x,y;
        scanf("%d%d%d",&k,&x,&y);
        if(k==1)
        {
            if(x>y)
            swap(x,y);
            printf("%d\n",ask(1,x,y).data);
        }else
        {
            change(1,x,y);
        }
    }
    return 0;
}