线段树

✍ dations ◷ 2025-02-24 02:24:07 #数据结构

线段树（英语：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)，则其需符合以下条件：

相关

颌颚（英语：Jaw），在解剖学中，指在嘴部入口处相对的铰接式结构，最常见的用途是用来进食与咀嚼食物。在大多数的动物身上，都拥有这个解剖结构。在人体解剖学中，又称颌，指嘴部的上下骨骼与
奥斯坎语奥斯坎语是奥斯坎人所操的语言，它是属于印欧语系意大利语族萨贝利克语支的，同语支的还有拉丁-法利希语和翁布里亚语，奥斯坎人分布于萨莫奈、坎帕尼亚、卢卡尼亚、阿布鲁索。奥
多媒体多媒体（Multimedia），在电脑应用系统中，组合两种或两种以上媒体的一种人机交互式资讯交流和传播媒体。使用的媒体包括文字、图片、照片、声音（包含音乐、语音旁白、特殊音效）、动画
轻率概化轻率概化（hasty generalization），又称不当概化（inappropriate generalization）、错误概化（faulty generalization）、范例肯证（proof by example）等等，是一种非形式谬误，指未充分考虑一
发起进攻波罗的海 – 黑海 – 北极 – (跳马 – PQ-17船团 – 仙境)1941年巴巴罗萨 – (比亚韦斯托克及明斯克 – 斯摩棱斯克 – 乌曼 – 列宁格勒 – 第一次基辅 – 塞瓦斯托波尔围
寒蝉效应 (法律)寒蝉效应（英语：Chilling Effect）法律用语，是指当下对言论自由的“阻吓作用”——即使是法律没有明确禁止的。然而，在一般情况下，寒蝉效应现在经常以法律或不明确行动施加不必要的
朝日放送集团控股朝日放送集团控股股份有限公司（日语：朝日放送グループホールディングス株式会社／あさひほうそうグループホールディングス；英语：Asahi Broadcasting Group Holdings Corporatio
乌龙江大桥乌龙江大桥是中华人民共和国福建省福州市建造较早的大跨度预应力水泥T型钢构桥。乌龙江大桥位于福州市仓山区城门镇乌龙江边，与闽侯县祥谦镇隔江相望。1970年，国务院批转福建
新希波箭石新希波箭石（学名：），又名前箭石、新箭石，是生存于中白垩纪的一属箭石，生活在温暖的大陆棚海域中，数量很多，以触须捕捉小动物为食。其化石分布于欧洲、北非、阿塞拜疆、莫桑比克和美国
英格·蒙内英格·蒙内（匈牙利语：Ingo Molnár），匈牙利软件程序员与骇客，在linux内核上有许多贡献，也拥有自己的linux分支版本。对于操作系统的安全性与效能提升方面，他的声名卓著。英格·蒙内