[数据结构]线段树

· · 题解

接下来我将结合\sf{gif}图具体讲讲线段树

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为 O(\log N) 。而未优化的空间复杂度为 2N ，因此有时需要离散化让空间压缩。

用途

在 \sf\ O(\log N) 的时间复杂度内实现：

单点修改、区间修改、区间查询\sf\ etc.

线段树维护的信息需要满足可加性，如果使用标记，标记也要满足可加性。

实现过程

基本结构与建树

有个数组 \sf\ a=\{10,11,12,13,14\} 要进行区间求和操作

怎么把这个数组存到线段树中呢？

设\sf\ d[i]是线段树中的结点。

如果 \sf\ d[i] 表示的是区间 \sf\ [l,r]

\sf\ d[i]$ 的左儿子节点表示的是区间 $\sf\ [l, \frac{l+r}{2} ]

如何实现？

如图 

#define leaf (l==r)
void build(int l,int r,int p)
{
    if(leaf)
    {
        d[p]=a[s];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls(p));
    build(mid+1,r,rs(p));
    d[p]=d[ls(p)]+d[rs(p)];
}

关于线段树的空间:

如果采用\sf\ 2p 是 \sf\ p 的左儿子，\sf\ 2p+1 是 \sf\ p 的右儿子的存储方式(堆存储)，则\sf\ d 数组的长度应为\sf\ 2^{\left\lceil\log{n}\right\rceil+1}，亦即取 2 的幂中第一个大于等于 \sf\ n 的幂并将其乘二作为\sf\ d数组的长度。

一般来说，开四倍是怎么样都够了的，但是在卡空间的题里要进行类似于动态开点的操作。

区间查询

区间查询，比如求区间 \sf\ [l,r] 的和的操作。

比如查询区间\sf\ [3,5]，把 \sf\ [3,5] 拆成 \sf\ [3,3] 和 \sf\ [4,5] 就行了。

int getsum(int l,int r,int l_now,int r_now,int p)
{
    //[l,r]为查询区间,[l_now,r_now]为当前节点包含的区间,p为当前节点的编号
    if(l<=l_now&&r_now<=r)
    {
        return d[p];//当前区间为询问区间的子集时直接返回当前区间的和
    }
    int mid=(l_now+r_now)>>1;
    int sum=0;
    if(l<=mid)
    {
        sum+=getsum(l,r,l_now,mid,ls(p));
    }
    //如果左儿子代表的区间[l,m]与询问区间有交集,则递归查询左儿子
    if(r>mid)
    {
        sum+=getsum(l,r,mid+1,r_now,rs(p));
    }
    //如果右儿子代表的区间[m+1,r]与询问区间有交集,则递归查询右儿子
    return sum;
}

主要思路是把区间拆成左右区间，再分别处理。(分治)

区间修改&懒标记

修改区间\sf\ [l , r]需要进行打懒标记的操作来减少时间消耗。

设一个数组 \sf\ laz ， \sf\ laz[i] 表示编号为 \sf\ i 的节点的懒标记。

区间修改（区间加）:

void interval_add(int l,int r,int val,int l_now,int r_now,int p)
{
    //[l,r]为修改区间,val为被修改的元素的变化量,[l_now,r_now]为当前节点包含的区间,p为当前节点的编号
    if(l<=l_now&&r_now<=r)
    {
        d[p]+=(r_now-l_now+1)*val;
        laz[p]+=val;
        return;
    }//当前区间为修改区间的子集时直接修改当前节点的值,然后打标记,结束修改
    int mid=(l_now+r_now)/2;
    if(laz[p]&&!leaf)
    {
        //如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
        d[ls(p)]+=laz[p]*(mid-l_now+1);
        d[rs(p)]+=laz[p]*(r_now-mid);

        laz[ls(p)]+=laz[p];
        laz[rs(p)]+=laz[p];//将标记下传给子节点
        laz[p]=0;//清空当前节点的标记
    }
    if(l<=mid)
    {
        interval_add(l,r,val,l_now,mid,ls(p));
    }
    if(r>mid)
    {
        interval_add(l,r,val,mid+1,r_now,rs(p));
    }
    d[p]=d[ls(p)]+d[rs(p)];
}

区间查询（求和）:

int getsum(int l,int r,int l_now,int r_now,int p)
{
    //[l,r]为查询区间,[l_now,r_now]为当前节点包含的区间,p为当前节点的编号
    if(l<=l_now&&r_now<=r)
    {
        return d[p];//当前区间为询问区间的子集时直接返回当前区间的和
    }
    int mid=(l_now+r_now)>>1;
    int sum=0;
    if(l<=mid)
    {
        sum+=getsum(l,r,l_now,mid,ls(p));
    }
    //如果左儿子代表的区间[l,m]与询问区间有交集,则递归查询左儿子
    if(r>mid)
    {
        sum+=getsum(l,r,mid+1,r_now,rs(p));
    }
    //如果右儿子代表的区间[m+1,r]与询问区间有交集,则递归查询右儿子
    return sum;
}

如果要实现区间赋值，把所有 += 替换成 = 即可

(除sum+=getsum(l,r,mid+1,r,rs(p) )

void interval_value(int l,int r,int val,int l_now,int r_now,int p)
{
    if(l<=l_now&&r_now<=r)
    {
        d[p]=(r_now-l_now+1)*val;
        laz[p]=val;
        return ;
    }
    int mid=(l_now+r_now)>>1;
    if(laz[p])
    {
        d[ls(p)]=laz[p]*(mid-l_now+1);
        d[rs(p)]=laz[p]*(r_now-mid);
        laz[ls(p)]=laz[rs(p)]=laz[p];
        laz[p]=0;
    }
    if(l<=mid)
    {
        interval_value(l,r,val,l_now,mid,ls(p));
    }
    if(r>mid)
    {
        interval_value(l,r,val,mid+1,r_now,rs(p));
    }
    d[p]=d[ls(p)]+d[rs(p)];
}
int getsum(int l,int r,int l_now,int r_now,int p)
{
    if(l<=l_now&&r_now<=r)return d[p];
    int mid=(l_now+r_now)>>1;
    if(laz[p])
    {
        d[ls(p)]=laz[p]*(mid-l_now+1);
        d[rs(p)]=laz[p]*(r_now-mid);
        laz[ls(p)]=laz[rs(p)]=laz[p];
        laz[p]=0;
    }
    int sum=0;
    if(l<=mid)
    {
        sum=getsum(l,r,l_now,mid,ls(p));
    }
    if(r>mid)
    {
        sum+=getsum(l,r,mid+1,r_now,rs(p));
    }
    return sum;
}

优化

小练1.LuoGu3372:线段树1

小练2.LuoGu3373:线段树2