线段树 订阅
线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,实际应用时一般还要开4N的数组以免越界,因此有时需要离散化让空间压缩。 展开全文
线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,实际应用时一般还要开4N的数组以免越界,因此有时需要离散化让空间压缩。
信息
时间复杂度
log(n)(建树为O(n))
外文名
Segment Tree
领    域
数据结构
中文名
线段树
功    能
单点、区间的修改、查询
学    科
数据结构
线段树定义
线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。 [1]  对于线段树中的每一个非叶子节点[a,b],它的左儿子表示的区间为[a,(a+b)/2],右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树,最后的子节点数目为N,即整个线段区间的长度。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,因此有时需要离散化让空间压缩。
收起全文
精华内容
下载资源
问答
  • 线段树

    2021-01-18 01:28:00
    文章目录一、线段树二、线段树的基本内容三、线段树的基本操作 一、线段树 1、线段树的树形结构: 线段树是一种二叉搜索树,什么叫做二叉搜索树,首先满足二叉树,每个结点度小于等于二,即每个结点最多有两颗子树...


    一、线段树

    1、线段树的树形结构:
    线段树是一种二叉搜索树,什么叫做二叉搜索树,首先满足二叉树,每个结点度小于等于二,即每个结点最多有两颗子树,何为搜索,我们要知道,线段树的每个结点都存储了一个区间,也可以理解成一个线段,而搜索,就是在这些线段上进行搜索操作得到你想要的答案。
    2、线段树的应用:
    线段树的适用范围很广,可以在线维护修改以及查询区间上的最值,求和。更可以扩充到二维线段树(矩阵树)和三维线段树(空间树)。对于一维线段树来说,每次更新以及查询的时间复杂度为O(logN)。
    3、线段树和其他RMQ算法的区别:
    常用的解决RMQ问题有ST算法,二者预处理时间都是O(NlogN),而且ST算法的单次查询操作是O(1),看起来比线段树好多了,但二者的区别在于线段树支持在线更新值,而ST算法不支持在线操作。
    线段树不但可以用来处理RMQ问题和求和问题,而且其实线段树的功能远远不止如此,要熟练的理解线段这个概念才能更加深层次的理解线段树。

    二、线段树的基本内容

    每个叶子结点的值就是数组的值,每个非叶子结点的度都为二,且左右两个孩子分别存储父亲一半的区间。每个父亲的存储的值也就是两个孩子存储的值的最大值。

    代码:

    const int maxn = 100005;
    int a[maxn],t[maxn<<2];       
    
    void Pushup(int k){       
        t[k] = max(t[k<<1],t[k<<1|1]);
    }
    
    void build(int k,int l,int r){   
        if(l == r)    
            t[k] = a[l];
        else{
            int m = l + ((r-l)>>1);
            build(k<<1,l,m);    
            build(k<<1|1,m+1,r);    
            Pushup(k);    
        }
    }
    

    三、线段树的基本操作

    1.点更新:

    代码:

    //递归方式更新 updata(p,v,1,n,1);
    void updata(int p,int v,int l,int r,int k){    
        if(l == r)   
            a[k] += v,t[k] += v;    
        else{
            int m = l + ((r-l)>>1);   
            if(p <= m)  
                updata(p,v,l,m,k<<1);
            else    
                updata(p,v,m+1,r,k<<1|1);
            Pushup(k);    
        }
    }
    

    2.区间查询:

    //递归方式区间查询 query(L,R,1,n,1);
    int query(int L,int R,int l,int r,int k){    
        if(L <= l && r <= R)   
            return t[k];
        else{
            int res = -INF;    
            int mid = l + ((r-l)>>1);    
            if(L <= m)    
                res = max(res, query(L,R,l,m,k<<1));
            if(R > m)   
                res = max(res, query(L,R,m+1,r,k<<1|1));
    
            return res;    
        }
    }
    

    3.区间更新:
    树状数组中的区间更新我们用了差分的思想,而线段树的区间更新相对于树状数组就稍微复杂一点,这里我们引进了一个新东西,Lazy_tag,字面意思就是懒惰标记的意思,实际上它的功能也就是偷懒= =,因为对于一个区间[L,R]来说,我们可能每次都更新区间中的没个值,那样的话更新的复杂度将会是O(NlogN),这太高了,所以引进了Lazy_tag,这个标记一般用于处理线段树的区间更新。
    线段树在进行区间更新的时候,为了提高更新的效率,所以每次更新只更新到更新区间完全覆盖线段树结点区间为止,这样就会导致被更新结点的子孙结点的区间得不到需要更新的信息,所以在被更新结点上打上一个标记,称为lazy-tag,等到下次访问这个结点的子结点时再将这个标记传递给子结点,所以也可以叫延迟标记。
    也就是说递归更新的过程,更新到结点区间为需要更新的区间的真子集不再往下更新,下次若是遇到需要用这下面的结点的信息,再去更新这些结点,所以这样的话使得区间更新的操作和区间查询类似,复杂度为O(logN)。

    void Pushdown(int k){   
        if(lazy[k]){    
            lazy[k<<1] += lazy[k];   
            lazy[k<<1|1] += lazy[k];    
            t[k<<1] += lazy[k];        
            t[k<<1|1] += lazy[k];    
            lazy[k] = 0;    
        }
    }
    
    //递归更新区间 updata(L,R,v,1,n,1);
    void updata(int L,int R,int v,int l,int r,int k){    
        if(L <= l && r <= R){    
            lazy[k] += v;    
            t[k] += v;    
        }
        else{
            Pushdown(k);    
            int m = l + ((r-l)>>1);
            if(L <= m)    
                update(L,R,v,l,m,k<<1);
            if(m < R)    
                update(L,R,v,m+1,r,k<<1|1);
            Pushup(k);    
        }
    }
    

    注意看Pushdown这个函数,也就是当需要查询某个结点的子树时,需要用到这个函数,函数功能就是更新子树的lazy值,可以理解为平时先把事情放着,等到哪天要检查的时候,就临时再去做,而且做也不是一次性做完,检查哪一部分它就只做这一部分。是不是感受到了什么是Lazy_tag,实至名归= =。

    值得注意的是,使用了Lazy_tag后,我们再进行区间查询也需要改变。区间查询的代码则变为:

    //递归方式区间查询 query(L,R,1,n,1);
    int query(int L,int R,int l,int r,int k){    
        if(L <= l && r <= R)    
            return t[k];
        else{
            Pushdown(k);    
            int res = -INF;    
            int mid = l + ((r-l)>>1);    
            if(L <= m)    
                res = max(res, query(L,R,l,m,k<<1));
            if(R > m)   
                res = max(res, query(L,R,m+1,r,k<<1|1));
    
            return res;    
        }
    }
    

    其实变动也不大,就是多了一个临时更新子树的值的过程。

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 79,587
精华内容 31,834
热门标签
关键字:

线段树