线段树

线段树介绍🌳

线段树是具有树的数据结构，用于处理区间问题，并拥有O(log n)级别时间复杂度的算法。

1.1 分块思想

线段树利用到了分块思想，那分块思想是什么呢？简单来说，分块思想是将一段序列分为有穷个小块，当我们要查询某一个区间的和时，我们总是可以表示成k个分块与m个单个元素的并。线段树在分块思想的基础上，将每一个“块”利用树的数据结构储存，提高了查找效率与修改效率。

1.2 线段树的限制

1.在最坏的情况下，线段树合并的时间次数是要大于分块的合并次数 n^1/2。

2.线段树只能用于维护带有结合律的信息，例如区间最值、区间和、区间异或这类，如果不带有结合律，则不能用线段树维护。但是分块要灵活的多，可以维护很多别的东西，功能性强。

3.越暴力的算法可以支持的操作越多，功能性越强。

线段树的构造实现✨

2.1 建树与维护

由二叉树的性质可知，对于一个节点u，它的左儿子为2 * u，它的右儿子为2 * u + 1。

我们根据这个性质，写一个查找左右儿子的函数：

inline int ls(int u){return u<<1;}//左儿子
inline int rs(int u){return u<<1|1;}//右儿子
//inline 可以有效防止无需入栈的信息入栈，节省时间和空间

有了这个之后，我们根据要维护的节点，来维护线段树

void pushup_sum(int u){
    t[u]=t[ls(u)]+t[rs(u)];
}//向上维护区间和

void pushup_min(int u){//维护区间最大值最小值
    t[u]=min(t[ls(u)],t[rs(u)]);//返回最小值
    //t[u]=maxt[ls(u)],t[rs(u)]);//返回最大值 如果有需要
}

有了pushup，我们就可以根据它来递归建树了。在电脑中的递归实际上是先向底层递归，然后从底层向上回溯，所以开始递归时，必然先去整合子节点的信息，由此我们就验证了递归建树的正确性。

从这里可以看出，线段树必须要满足结合律，因为它包括了pushup这个函数。

以下是递归建树的代码：

#define ll long long
void build(ll u,ll l,ll r){
    if(l==r){t[u]=a[l];return;}//t数组为要维护的信息，a为读入的数据
    ll mid=(l+r)>>1;
    build(ls(u),l,mid);
    build(rs(u),mid+1,r);
    pushup(u);//在回溯时维护，pushup可以是你任何想维护的操作
}

自此，我们就递归建立好了线段树。

2.2 区间修改

因为单点修改是区间修改的子问题，即区间长度为1的修改，所以我们在这里不再讨论单点修改。

对于区间操作，我们引入一个概念——**懒标记(lazy tag)**。为什么我们叫他懒标记呢，这是因为原本我们修改区间时需要通过先改变叶子节点的值，然后不断向上递归修改祖先的节点，时间复杂度最高可以达到O(nlog n)。当我们引入懒标记之后，区间复杂度降到了O(log n)。

具体来说，懒标记的作用时记录每次每个节点要更新的值。在此我们利用到了线段树的优点——传递式记录。

也就是说，当我们修改整个区间时，我们将懒标记记录在公共祖先节点上；只修改一部分，那么我们就记录在这公共部分的祖先上。

此时，因为我们要向下传导，我们引入一个新的pushdown函数，如下所示：

inline void maketag(ll u,ll l,ll r,ll k){//k为要加的值
    tag[u]=tag[u]+k;
    t[u]=t[u]+k*(r-l+1);
    //tag为懒标记数组
}
//我们可以看出，maketag函数唯一的目的是记录当前节点所代表的区间
inline void pushdown(ll u,ll l,ll r){
    ll mid=(l+r)>>1;
    f(ls(u),l,mid,tag[u]);
    f(rs(u),mid+1,tag[u]);
    tag[u]=0;
    //每次更新两个子节点，然后向下传递
}
//查询要修改的区间
bool InRange(ll L,ll R,ll l,ll r){
    return (l<=L)&&(r>=R);
}
bool OutofRange(ll L,ll R,ll l,ll r){
    return (L>r)||(R<l);
}
//更新
inline void update(ll u,ll L,ll R,ll l,ll r,ll k){
    if(InRange（L,R,l,r){
        maketag(u,L,R,k);
    }else if(!OutofRange(L,R,l,r)){
        int mid=(L+R)>>1;
        pushdown(u,L,R);//将当前节点的标记往下传递
        update(ls(u),L,M,l,r,k);
        update(rs(u),M+1,R,l,r,k);
        pushup(u);//记得更新值
    }
}

2.3 区间查询

最后，我们就可以进行对区间的查询了，代码如下：

ll query(ll u,ll L,ll R,ll l,ll r,ll k){
     if(InRange（L,R,l,r){
        return t[u];
    }else if(!OutofRange(L,R,l,r)){
        int mid=(L+R)>>1;
        pushdown(u,L,R);//查询的时候也要将当前节点的标记往下传递
        return query(ls(u),L,M,l,r)+query(rs(u),M+1,R,l,r);
    }else return 0;
}

由此，我们就实现了线段树的主要功能，在面对具体算法题目时，需要灵活运用线段树。

参考

1.《深入浅出程序设计竞赛》进阶篇

2.洛谷P3372题解，皎月半洒花