史上最详细的线段树教程

问题提出:

现有如下的问题,给定一个的序列,实现以下操作:

①更新序列的某个值。

②查询序列的某个区间的最小值(最大值、区间和)线段树常用于解决区间统计问题。求最值,区间和等操作均可使用该数据结构,本篇以求最小值为例。

③更新序列的某个区间内的所有值。

对于求最小值,我们很容易想到的算法就是。更新序列的某个值直接找到该值,更新,时间复杂度是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 ·>>

发表回复

相关推荐

必胜客兼职体验

一、面试 选择一个人少的时间去面试,一般都会安排好,我是3点半去的,面试10分钟左右,面试的人是一位小姐姐,讲话很温柔, ...

· 15分钟前

考研一般怎么报名?在哪里报?

考研报名包括网上报名和现场确认两个阶段。网上报名阶段需登录教育部规定的官方网站进行报名,报名网站为“中国研究生招生信 ...

· 23分钟前

公司培訓管理制度模板分享

俗話說,無規矩不成方圓;凡事預則立,不預則廢;創業不是一件容易的事,對外我們需要去開拓市場,對內我們需要穩定、團結、...

· 24分钟前

关于蜜蜂和蜂产品的那些事 1 ——蜜蜂的类别

​ 一年蜂忙季即将结束,得花偷闲又开侃。 蜜蜂是自然中常见的生物,是昆虫界群体生活的代表,它们数量庞大群居在一起,过著 ...

· 36分钟前

英语课可以叫自己 Dio 吗? 网络流行语科普-dio是什么意思?

dio,就是嚣张傲慢,又玩世不恭的感觉。 源自《JoJo的奇妙冒险》第三部星辰十字军中的反派角色之一的迪奥·布兰度(dio),迪 ...

· 40分钟前