线段树

✍ dations ◷ 2025-08-24 19:21:09 #数据结构

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

相关

J01CA·B·C·D·G·H·QI·J·L·M·N·P·R·S·VATC代码J01（抗菌药）是解剖学治疗学及化学分类系统的一个药物分组，这是由世界卫生组织药物统计方法整合中心（The WHO Collaboratin
四环素类抗生素四环素类抗生素，一个广效抗生素（Broad-spectrum antibiotic）药物家族的泛称，因其氢化并四苯母核而得名。本类药物抗菌谱广，对革兰氏阴性菌、革兰氏阳性菌、螺旋体、衣原体、立克
呼气流量峰值峰值呼气流量（英文：peak expiratory flow，PEF），也称峰值呼气流量测定（英文：peak expiratory flow rate, PEFR）是一个人的最大呼气速度，用峰值流量计测量，一个用于监测一个人呼吸空气能
冒口冒口（riser）也称为补给口（feeder），是在金属铸造（英语：metal casting）中为了避免因材料收缩（英语：Shrinkage (casting)）而产生缩孔或是不平整处，额外所增加的材料储腔，不是最后铸件成品的
东东在汉语中有多个意义：
弗兰茨二世弗朗茨二世（德语：Franz II，1768年2月12日－1835年3月2日），神圣罗马帝国的末代皇帝(1792年-1806年在位)，奥地利帝国的第一位皇帝(1804年-1835年在位，称弗朗茨一世，德语：Franz I)。神圣罗
生态经济学 (学术期刊)《生态经济学》（Ecological Economics）是一份1989年起发行的学术期刊。该期刊每月出版一次，内容以生态经济学为主。目前，期刊的主编是美国达特茅斯学院的Richard B. Howarth。据
英属索马里兰英属索马里兰（英语：British Somaliland），正式名称是英属索马里兰保护国，是英国在非洲之角东北部的一个殖民地。首府哈尔格萨。二战时期1940年8月，意大利自意属东非占领英属索马里
艾达卜艾达卜（阿拉伯语：أدب‎，罗马化：Adab）是指既定的伊斯兰礼仪：“有教养、举止优雅、有公德、彬彬有礼、端庄得体、慈悲为怀”。艾达卜的适用范围及细节因应文化的不同而有不同的解
李金华 (外交官)李金华（1932年9月－），女，生于山东济南，祖籍河北黄骅，中华人民共和国外交官。毕业于南开大学历史系。曾任中国驻新西兰大使，外交部新闻司副司长等职；同时，她还是中华人民共和国外交部首