线段树,一段段的树

线段树这个名称充分体现了程序员们的直男思维,名字中蕴含着线段树的核心。线段树与区间树类似,将一个区间划分为一些单元区间,将每个单元区间存储在节点中。

线段树是一种二叉搜索树。什么是二叉搜索树?首先要满足二叉树的定义,每个节点的度都小于等于2。其次作为搜索树,在树上进行搜索就可以得到答案。

线段树有很大的使用范围,可以用于线维护修改和查询区间上的最值、求和,并且可以扩充为二维线段树(矩阵树)和三维线段树(空间树)。在线段树上的每一次更新和查询的时间复杂度都是$O\left(n\log n\right)$。

比起大堆的文字,果然还是图示比较容易理解线段树的含义。来人!上图!

xianduanshu1

这是一个只有聪明人才能看见节点的线段树哒!你没有看见?emmmm,因为它确实是空的。让我们给它一个数列A[1:6]={1,8,6,4,3,5}。首先,根节点储存整个区间,接着我们将这个区间像百奇一样掰断!左一半,右一半。于是根节点的左右两个节点分别分到了[1:3]、[4:6]这两个区间。以此类推,我们对每一个节点都进行这样的操作,直到无法分割为止。于是是我们得到了这样的一棵树。

xianduanshu2

接着从叶子节点求出我们要求的值(这里以最大值做示范),可以看出父亲的值就是两个子节点存储的值中的最大值,于是我们从底部向上回溯定义。

xianduanshu3

这样的一棵树就是线段树。那该任何存储这棵树呢?对于一个区间,最重要的显然是l,r这两个范围。但是由于l和r可以通过递归传参得到,所以我们便可以考虑使用数组来存储线段树。既然要用数组,那我们得先给每一个节点编上号。

bianhaonew

这样的编号方式,我们不难发现其中规律:

$left=father*2$

$right=father*2+1$

这样线段树父子节点之间在数组中的下标关系就可以确定了,由此也可以看出无优化的线段树需要$2* 2^{k}$的空间,所以一般开$4* n$的空间防止RE。而在代码中,往往使用位运算来计算节点的下标,因为位运算的速度更快(玄学)。

建树代码:

void push_up(int now)
{
    t[now]=t[now<<1]+t[now<<1|1]; //写函数是好习惯
    return;
}
void build(int now,int l,int r)
{
    if(l==r)
    {
        t[i]=d[i]; //如果区间大小为1,则最大值确定
        return;
    }
    int m=(l+r)/2;
    build(now<<1,l,m); //向下搜索
    build(now<<1,m+1,r);
    push_up(now); //更新父节点
    return;
}

发表于 2019-07-23 10:27:48 in 数据结构