线段树

✍ dations ◷ 2025-05-18 19:14:51 #数据结构

线段树（英语：Segment tree）是一种二叉树形数据结构，1977年由Jon Louis Bentley发明，用以存储区间或线段，并且允许快速查询结构内包含某一点的所有区间。

一个包含 $n {\displaystyle n}$ $n$ 个区间的线段树，空间复杂度为 $O(n)$ $O(n)$ ，查询的时间复杂度则为 $O(\log n+k)$ $O(\log n+k)$ ，其中 $k {\displaystyle k}$ $k$ 是符合条件的区间数量。

此数据结构亦可推广到高维度。

本处以一维的线段树为例。

令S是一维线段的集合。将这些线段的端点坐标由小到大排序，令其为 $x_{1},x_{2},\cdots ,x_{m}$ $x_{1},x_{2},\cdots ,x_{m}$ 。我们将被这些端点切分的每一个区间称为“单位区间”（每个端点所在的位置会单独成为一个单位区间），从左到右包含：

线段树的结构为一个二叉树，每个节点都代表一个坐标区间，节点N所代表的区间记为Int(N)，则其需符合以下条件：

相关

电解质不平衡电解质在生物体的自平衡维持上相当的重要。电解质可调节心臓及神经机能、输送氧气、维持体液平衡（英语：fluid balance）及酸碱平衡等。电解质的不平衡可能因为以下原因而产生：过
社会福利福利主义主张政府收取缴纳高额的税收，并提供高福利乃至一手承办教育、卫生之类涉及公共服务的事业。一方面，福利主义国家有明显的社会主义性质，现代的福利国家主要由中左派政党
节气节气指二十四时节和气候，是中国古代用来指导农事之历法历注。东亚传统夏历（农历）是一种“阴阳合历”，同时根据日、月运行制定，“阴”是以朔望月为基准确定，“阳”是以地球自冬至绕
婆罗米系文字婆罗米系文字或印度系文字，是印度孔雀王朝的婆罗米文衍生而来的一种书写系统，属于元音附标文字（Abugida）。其被广泛使用于南亚、东南亚、部分中亚及东亚地区。是目前世界上第四
接触法接触法（Contact process）是目前工业上制造硫酸的主要方法，整个方法主要包括四步：通过硫化矿或硫黄的高温焙烧产生二氧化硫气体；二氧化硫与氧气在高温催化下通过可逆反应化合生成
拉萨·奥本海拉萨·奥本海（Lassa Francis Lawrence Oppenheim，1858年3月30日－1919年10月7日），德国法学家，被誉为“现代国际法之父”。奥本海生于德国法兰克福附近的温德肯，求学于柏林洪堡大学、
吻 (画)《吻》（德语：Der Kuss）是奥地利象征主义画家古斯塔夫·克林姆的代表画作之一，是他在黄金时期所创作的作品，他在此时期常使用金箔来作画。《吻》是一幅正方形的画作，呈现出一对相拥
高桥直纯高桥直纯（1971年12月6日－）是日本岩手县奥州市出身的男性歌手、声优，原本是Realize Records Towers所属，2007年11月1日起改为DWANGO所属。经常与服装公司h.NAOTO合作。声优代表作
硝酸六脲合铁(III)硝酸六脲合铁(III)是一种配位化合物，化学式为(NO3)3，是黄绿色或浅绿色固体。其俗名为尿素铁。硝酸六脲合铁(III)可由硝酸铁九水合物和尿素按1:6.2化学计量比反应得到，水溶液法
绝缘电阻测试绝缘电阻测试是测试和检验电气设备的绝缘性能的常规手段，同时也是高压绝缘试验的预备试验。和耐压测试相似，它是把最高可达1000V的直流电压施加到需要测试的两点。绝缘电阻测