线段树

✍ dations ◷ 2025-12-09 16:23:14 #数据结构

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

相关

爱德华一世爱德华一世（英文：Edward I，1239年6月17日－1307年7月7日），英格兰国王，俗称“长腿（Longshanks）”“长腿爱德华”、又称“苏格兰人之锤（Hammer of the Scots）”，因征服威尔士和几乎征服苏格
ACU英联邦大学协会（英语：Association of Commonwealth Universities，缩写：ACU）是一个英联邦体系的国家之下，有480余所成员大学的教育相关组织，其宗旨是“我们为我们的成员机构服务，以提
屠房屠房是屠宰动物的设施。据统计，平均每只动物的40-45%可供食用，10-15%会被弃置，剩余的40-45%会被制成副产品，例如：皮革、肥皂、蜡烛、明胶等。20世纪后期，美国屠房的设计很大程度受
三氟乙酸三氟乙酸（化学式：CF3COOH），缩写TFA，是乙酸的全氟衍生物，也是最简单的全氟羧酸类化合物。无色挥发性发烟液体，与乙酸气味类似，有吸湿性和刺激性臭味。与水、氟代烃、甲醇、乙醇、乙醚
工程地质学工程地质学（英语：Engineering geology）是一门应用地质学的原理为工程应用服务的学科，主要研究内容涉及地质灾害，岩石与第四纪沉积物，岩体稳定性，地震等。工程地质学广泛应用于工程
里夏德·冯·魏茨泽克里夏德·卡尔·冯·魏茨泽克男爵（德语：Dr. Richard Karl Freiherr von Weizsäcker，1920年4月15日－2015年1月31日），是德国的政治家。德国基督教民主联盟成员，曾于1981年任西柏林市
媾和和平条约，简称和约，是敌对双方所签署的一种条约，主要用以正式结束战争和武装冲突，签订双方通常是国家、政府或政治实体。当条约签署完成之后，双方的敌对状态将会结束。此与停战协
MPEG-1MPEG-1是MPEG组织制定的第一个视频和音频有损压缩标准，也是最早推出及应用在市场上的MPEG技术，其原来主要目标是在CD光盘上记录影像，后来被广泛应用在VCD光盘。视频压缩算法于1
亲代投资在进化生物学和进化心理学中，亲代投资是指亲代为增加后代适应度而付出的资源，以牺牲亲代投资其他适应度成分的能力为代价。适应度的成分包括现存后代的福祉、亲代的未来生殖能
PHPPHP（全称：PHP：Hypertext Preprocessor，即“PHP：超文本预处理器”）是一种开源的通用计算机脚本语言，尤其适用于网络开发并可嵌入HTML中使用。PHP的语法借鉴吸收C语言、Java和Perl等