线段树_线段树的两个节点的作用

作者：我家自动化 | 2024-03-02 11:06:49

踩

线段树的两个节点的作用

1.线段树的每个节点都代表一个区间

2.线段树具有唯一的根节点，代表的区间是整个统计范围

3.线段树的每个叶子节点都代表一个长度为1的元区间

4.对于每个内部节点【l,r】，他的左子节点[l,mid],有子区间为[mid+1,r]

上图展示了一棵线段树。数的深度为logN，我们可以按照与二叉堆类似的“父子2倍”节点编号方法：

1.根节点编号为1.

2.编号为x的节点左子节点为x*2，右节点标号为x*2+1.那么我们就可以使用一个struct数组来保存线段树。

线段树的建树：

线段树的基本用途是对序列进行维护，支持查询与修改指令。给定一个长度为N的序列A，我们就可以在区间[1,N]上建立一颗线段树。每个叶子节点[i,i]保存a[i]的值。线段树的二叉树结构可以很方便的从下往上传递信息。以区间最大值问题为例，记

dat(l,r)等于max(l<=i<=r)

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/180084