线段树

✍ dations ◷ 2024-12-23 06:11:03 #数据结构

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

相关

多肽肽（英语：peptide，来自希腊文的“消化”），旧称胜，即胜肽，又称缩氨酸，是天然存在的小生物分子，介于氨基酸和蛋白质之间的物质。由于氨基酸的分子最小，蛋白质最大，而它们则是氨基酸单体组
瞳孔瞳孔（英语：Pupil）又称瞳神，是眼球血管膜的前部虹膜中心的圆孔。沿瞳孔环形排列的平滑肌叫瞳孔括约肌，收缩时使瞳孔缩小，沿瞳孔放射状排列的平滑肌叫瞳孔放大肌，松弛时使瞳孔放大，调
普鲁卡因胺普鲁卡因胺（INN：Procainamide，发音： /proʊˈkeɪnəmaɪd/）是一种Ia类抗心律失常药，用于治疗心律不整。普鲁卡因胺在1951年由百时美施贵宝研制成功。它在1950年6月2日被美国食品
马克·吕特马克·吕特（荷兰语：Mark Rutte，荷兰语发音：.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Code2000","
锅炉锅炉是一种利用燃料燃烧放出的热能或者其他热能加热水或其他工质，以生产规定参数（温度、压力）的品质的蒸汽、热水或者其他工质的设备。锅炉常在热力发电厂或其他工业、民用生产
担幡买水担幡买水是儒家文化圈传统丧事时的仪式，有清洁死者的功能，由死者的至亲于丧礼中负责。担幡则指由死者的长子嫡孙提着引魂幡，代表引领亡灵升天。或谓出殡当日孝子手执木棍，棍端绑
费迪南·冯·哈布斯堡费迪南·兹沃尼米尔·冯·哈布斯堡（Ferdinand Zvonimir von Habsburg，1997年6月21日－），全名是费迪南·兹沃尼米尔·玛利亚·巴尔蒂斯·凯特·米夏埃尔·奥托·安塔尔·巴曼·莱昂
智利比索智利比索为智利流通货币。现在流通的比索发行于1975年，之前智利比索曾在1817年到1960年期间发行过。货币编号CLP。辅币单位为分，1比索=100分。
好莱坞往事《好莱坞往事》（英语：，或记作）是一部2019年美国和英国合拍的喜剧剧情片，由昆汀·塔伦蒂诺执导兼编剧。该片以群戏的方式呈现，其主演包括莱昂纳多·迪卡普里奥、布拉德·皮特、玛格
红光街道 (成都市)红光街道，原为红光镇，是中华人民共和国四川省成都市郫都区下辖的一个乡镇级行政单位。2019年12月，撤镇设街道，红光街道办事处驻高店路东段39号。红光街道下辖以下地区：三观村、红