線段樹(Segment Tree)
实际上还是称为区间树更好理解一些。
树：是一棵树，而且是一棵二叉树。
线段：树上的每个节点对应于一个线段(还是叫“区间”更容易理解，区间的起点和终点通常为整数)
同一层的节点所代表的区间，相互不会重叠。
叶子节点的区间是单位长度，不能再分了。
树：是一棵树，而且是一棵二叉树。
线段：树上的每个节点对应于一个线段(还是叫“区间”更容易理解，区间的起点和终点通常为整数)
同一层的节点所代表的区间，相互不会重叠。
叶子节点的区间是单位长度，不能再分了。
线段树是一棵二叉树，树中的每一个结点表示了一个区间[a,b]。a,b通常是整数。每一个叶子节点表示了一个单位区间。对于每一个非叶结点所表示的结点[a,b]，其左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2,b](除法去尾取整）。
线段树的基本用途：
线段树适用于和区间统计有关的问题。比如某些数据可以按区间进行划分，按区间动态进行修改，而且还需要按区间多次进行查询，那么使用线段树可以达到较快查询速度。
线段树适用于和区间统计有关的问题。比如某些数据可以按区间进行划分，按区间动态进行修改，而且还需要按区间多次进行查询，那么使用线段树可以达到较快查询速度。
线段树的构建
createSeg //以节点v为根建树、v对应区间为[l,r]
{
对节点v初始化
if (l!=r)
{
以v的左孩子为根建树、区间为[l,(l+r)/2]
以v的右孩子为根建树、区间为[(l+r)/2+1,r]
}
}
{
对节点v初始化
if (l!=r)
{
以v的左孩子为根建树、区间为[l,(l+r)/2]
以v的右孩子为根建树、区间为[(l+r)/2+1,r]
}
}
(浏览器似乎不太好用了，上面的代码点“插入代码”不管用，就直接贴出来了)
个人感觉线段树比较灵活，要多做一些题目才能对线段树有一个大概的掌握。
网上看见了一些线段树的资料，这里也贴出来。
网上看见了一些线段树的资料，这里也贴出来。
线段树(区间树)Segment Tree
沒有留言:
張貼留言