史上最详细的线段树教程
问题提出：
现有如下的问题，给定一个的序列，实现以下操作：
①更新序列的某个值。
②查询序列的某个区间的最小值(最大值、区间和)线段树常用于解决区间统计问题。求最值，区间和等操作均可使用该数据结构，本篇以求最小值为例。
③更新序列的某个区间内的所有值。
对于求最小值，我们很容易想到的算法就是。更新序列的某个值直接找到该值，更新，时间复杂度是O(1)；区间查询直接遍历该区间，时间复杂度是O(n)；区间修改的也是直接遍历该区间修改，时间复杂度是O(n)，在数据量特别大，操作比较多的时候，效率是很低的。另一种解法是这样的。构建一个二维数组，a[i][j]表示区间[i,j]的最小值。这样查询操作的复杂度为O(1)，但是这样的话，修改的复杂度也不低而且如果数据量特别大，O(n^2)的空间复杂度也是不容忽视的。这时候就需要我们是用线段树这种优秀的高级数据结构来解决了。
线段树：
我们以序列{5,9,7,4,6,1}为例子演示。这个序列构成的线段树是这样的。
从这颗树上我们可以了解线段树的这几个特点，线段树是一颗近似的完全二叉树，每个节点代表一个区间，节点的权值是该区间的最小值。根节点是整个区间。每个节点的左孩子是该节点所代表的的区间的左半部分，右孩子是右半部分。为方便起见，如果区间长度为奇数，则左孩子为较长的半部分。通过线段树，我们可以用O(logn)的时间复杂度完成查询和更新操作。当然，预处理的时间复杂度是O(n)。
线段树的构建：
我们将每一个节点封装到Node类中。
class Node//节点
{
int start;//区间的左端点
int end;//区间的右端点
int data;//该节点的值
int mark = 0;//延迟更新的标记
public Node(int start,int end)//构造方法中传入左端点和右端点
{
this.start = start;
this.end = end;
}
void addMark(int value)//做标记
{
this.mark+=value;
}
void clearMark()
{
this.mark = 0;
}
public String toString()
{
return start+"-"+end;
}
}
<< · Back Index ·>>
相关推荐
英语课可以叫自己 Dio 吗？ 网络流行语科普-dio是什么意思?
dio，就是嚣张傲慢，又玩世不恭的感觉。 源自《JoJo的奇妙冒险》第三部星辰十字军中的反派角色之一的迪奥·布兰度（dio），迪 ...