【转载】线段树区间合并小结

原地址：https://blog.csdn.net/sunyutian1998/article/details/79618316

个人感觉区间合并是线段树各种应用中变形最多也是比较难琢磨的一种

(以下以求01序列中最长连续1为例)

tree[cur].left代表以区间左端点为起点的连续段的长度 tree[cur].right代表右边 tree[cur].all代表该区间内最长的连续段

通过这三个变量的组合对于每一个区间一般有四个值供我们使用

1 tree[cur].left代表以该区间左端点为起点的连续段的长度(左连续段)

2 tree[cur].right代表以该区间右端点为终点的连续段的长度(右连续段)

3 tree[2*cur].right+tree[2*cur+1].left 代表包含该区间中点的连续段的长度 这是个隐含值(中间连续段)

4 tree[cur].all代表该区间内最长连续段 其值不止要从左右子节点的最长连续段中择最大 还要考虑该区间的中间连续段即 tree[cur].all=max(tree[2*cur].right+tree[2*cur+1].left,max(tree[2*cur].all,tree[2*cur+1].all));

   对于tree[cur].all的取值可以这样理解 如果两个子区间合并后产生了新的连续段 那一定是tree[2*cur].right+tree[2*cur+1].left的值 即中间连续段 如果没有那就只能在两个子区间的最长连续段择优了

区间合并关键在于pushup函数的构造详见代码注释(以求01序列中最长连续1为例)

void pushup(int cur)
{
    tree[cur].left=tree[2*cur].left;//当前区间的左区间的左端点肯定也是当前区间的左端点 所以以当前区间的左端点为起点的最长连续1长度肯定包含其左区间的对应值 这一部分值先记下来
    if(tree[cur].left==tree[2*cur].r-tree[2*cur].l+1) tree[cur].left+=tree[2*cur+1].left;//再判断一下当前这些连续的1是不是已经贯穿了整个左区间 和有区间接轨 如果是的话 必须把右孩子的对应值也加上(如果右孩子对应区间全为1 那么当前区间也会全为1 这种情况也是很有可能的)
 
    /*
    比如[1,8]区间 (1 1 1 1) (1 1 0 1)
    在未pushup时
    tree[2*cur].left==4,tree[2*cur].right==4,tree[2*cur].all==4
    tree[2*cur+1].left==2,tree[2*cur+1].right==1,tree[2*cur+1].all==2
    执行完tree[cur].left=tree[2*cur].left后tree[cur].left==4 但显然以当前区间的左连续段的长度还需要算上右区间中的一部分
    所以要执行tree[cur].left+=tree[2*cur+1].left 然后tree[cur].left==6即为正确结果
    */
 
    tree[cur].right=tree[2*cur+1].right;//右连续段的处理同上
    if(tree[cur].right==tree[2*cur+1].r-tree[2*cur+1].l+1) tree[cur].right+=tree[2*cur].right;
 
    tree[cur].all=max(tree[2*cur].right+tree[2*cur+1].left,max(tree[2*cur].all,tree[2*cur+1].all));
    //显然当前区间最长连续段要从左右区间的最长连续段取最大值 但这样就足够了吗?
    //tree[cur].all的值不止要从左右子区间的最长连续段中择最大 还要考虑该区间隐含的"中间连续段"
    /*
    比如[1,12]区间 (1 1 1 0 1 1) (1 1 0 1 1 1)
    在未pushup时
    tree[2*cur].left==3,tree[2*cur].right==2,tree[2*cur].all==3
    tree[2*cur+1].left==2,tree[2*cur+1].right==3,tree[2*cur+1].all==3
    只考虑从左右区间的最长连续段取最大值的话 即执行tree[cur].all=max(tree[2*cur].all,tree[2*cur+1].all)之后tree[cur].all==3
    但显然中间有四个连续的1被漏掉了
    */
    return;
}

下面是做过的一些类型题总结