Eternity

Until The End

线段树

发表于 更新于 分类于 ，
本文字数： 2.8k 阅读时长 ≈ 3 分钟

“我一步一步走向深处，寻找你的身影，又将你拉回——我们的起点”

线段树是用来维护区间权值的一种数据结构，根据同机房巨佬而言，一般需要使用线段树的题考点都不在线段树上，不过线段树真滴好用

线段树的操作：

Ⅰ.建树

我的习惯为使用结构体存储（就和链式前向星一样），也可以分开打：

1
2
3
4
5
struct SegmentTree
{
	int l,r,dat;
	//int tag;
}Tree[N<<2];

一般来说，线段树的数组需要开四倍 $N$ 空间，因为他比线性结构要多一层，而开四倍一般不会爆。

代码讲解：

对于其中之一 $Tree[p]$ 中：

$l$ 表示第p个编号所表示的区域起点为原线性结构的 $A_l$ ；

$r$ 表示第p个编号所表示的区域终点为原线性结构的 $A_r$ ；

子节点保证： $l=r$ ；

$dat$ 表示该区域的一个数据，一般视题目而定，且 $dat$ 的个数也不定。

$tag$ 可有也可不有（如果是区间修改的题一般都有），表示“懒惰标记”，之后详解。

$p$ 结点的子结点为 $p2$ 和 $p2+1$ ，一般在代码中写为 $p<<1$ 和 $p<<1|1$ 来节约时间（因为位运算时间复杂度＜乘法复杂度）

建树一般使用递归建树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline void underBuild(int p,int l,int r)
{
    Tree[p].l=l;
    Tree[p].r=r;
    if(l==r)		//到达子结点
    {
        Tree[p].dat=Val[l];
        return ;
    }
    int mid=(l+r)>>1;
    underBuild(p<<1,l,mid);
    underBuild(p<<1|1,mid+1,r);
    underPushUp(p);
}

Ⅱ.查询

以查询该区间权值和为例：

如果该结点在需要查询的区间内，返回该点权值；

如果不在搜索子结点，如果需要的 $l$ 比该结点的 $mid$ 小，则搜索 $(l,mid)$；如果需要的 $r$ 比该结点的 $mid$ 大，则搜索$(mid+1,r)$。

具体操作看函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
inline long long underQuery(int p,int l,int r)
{
    if(Tree[p].l>=l&&r>=Tree[p].r)
    {
        return Tree[p].dat;
    }
    underSpread(p);		//区间修改的操作，之后详解
    int mid=(Tree[p].l+Tree[p].r)>>1;
    long long val=0;
    if(l<=mid)
    {
        val+=underQuery(p<<1,l,r);
    }
    if(mid<r)
    {
        val+=underQuery(p<<1|1,l,r);
    }
    return val;
}

Ⅲ.单点修改

找到该点的编号，从下至上修改它的所有父结点直到，依然使用递归操作。

$dat$ 存储该区间的区间和：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
inline void underChange(int p,int v,int k)
{
    if(Tree[p].l==v&&Tree[p].r==v)
    {
        Tree[p].dat=k;			//到达子结点后修改dat值
        return ;
    }
    int mid=(Tree[p].l+Tree[p].r)>>1;
    if(v<=mid)
    {
        underChange(p<<1,l,r,k);
    }
    if(v>mid)
    {
        underChange(p<<1|1,l,r,k);
    }
    Tree[p].dat=Tree[p<<1].dat+Tree[p<<1|1].dat;
}

Ⅳ.向上传递（pushup）

即函数underPushUp，一般都是视题目而定。

以区间和为例：

1
2
3
4
inline void underPushUp(int p)
{
	Tree[p].dat=Tree[p<<1].dat+Tree[p<<1|1].dat;
}

似乎这个例子没什么说服力，不过的确是这样的。

Ⅴ.向下传递（pushdown/spread）

只限于懒惰标记。当我们需要改变该区间中的子区间才会向下传递，这样可以优化时间，否则每一次区间修改都会花费 $O(N)$ 的时间复杂度。

依然以区间和为例：

1
2
3
4
5
6
7
8
9
10
11
inline void underSpread(int p)
{
    if(Tree[p].tag)
    {
        Tree[p<<1].dat+=Tree[p].tag*(Tree[p<<1].r-Tree[p<<1].l+1);
        Tree[p<<1|1].dat+=Tree[p].tag*(Tree[p<<1|1].r-Tree[p<<1|1].l+1);
        Tree[p<<1].tag+=Tree[p].tag;
        Tree[p<<1|1].tag+=Tree[p].tag;
        Tree[p].tag=0;
    }
}

Ⅵ.区间修改

使用懒惰标记，可以让时间复杂度降到 $O(logN)$ 。

依然以区间和为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline void underModify(int p,int l,int r,int k)
{
    if(l<=Tree[p].l&&Tree[p].r<=r)
    {
        Tree[p].dat+=k*(Tree[p].r-Tree[p].l+1);
        Tree[p].tag+=k;
        return ;
    }
    underSpread(p);
    int mid=(Tree[p].l+Tree[p].r)/2;
    if(l<=mid)
    {
        underModify(p<<1,l,r,k);
    }
    if(r>mid)
    {
        underModify(p<<1|1,l,r,k);
    }
    Tree[p].dat=Tree[p<<1].dat+Tree[p<<1|1].dat;
}

一些练习

区间修改区间查找模板题

区间最大子段和模板题

P2574 XOR的艺术

区间求sin和，需要使用数学知识

卡常卡码风的毒瘤题

头图来源：
Warma

相关文章