线段树

✍ dations ◷ 2025-12-08 06:26:12 #数据结构

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

相关

旺代战争1795年6月24日 - 1796年3月29日 1799年10月15日 - 1800年1月18日旺代战争（法语：Guerre de Vendée），又称旺代暴动（法语：Révolte Vendéenne）、旺代叛乱（法语：Rébellion Vendéenne
个人个人（意大利语、西班牙语: Persona，英语、德语: Person，来自拉丁语: Persōna）是单独的人类个体的简称，相对应的是由多数人类个体组成的人民。亦是具有某种能力或属性的存在，如理
Sj音国际音标的 /ɧ/ 表示的是瑞典语中的sje音（sje-ljudet），它存在于瑞典语多数方言中，是个清擦音，但具体的发音部位仍然不能确定。该音有众多变体，音值随发音者年龄、方言而有一些不
维尔纳·法伊曼维尔纳·法伊曼（德语：Werner Faymann；1960年5月14日－），奥地利政治家、曾任奥地利总理。由于未得到奥地利社会民主党一致支持，维尔纳·法伊曼宣布辞去奥地利总理和该党领导人职务。
伯班克伯班克（英语：Burbank）是一座位于美国加利福尼亚州洛杉矶县中部的城市，是大洛杉矶地区的组成部分之一。伯班克被称为“世界媒体之都”（Media Capital of the World），包括国家广播公
甜甜私房猫《甜甜私房猫》为日本女性漫画家湖南彼方（こなみかなた）的一部和猫相关的漫画作品，2004年开始于讲谈社漫画杂志《Morning》连载至今，为黑白漫画；单行本则为全彩漫画。每章标题都
巴尔塔萨·加尔松巴尔塔萨·加尔松·雷亚尔（西班牙语：Baltasar Garzón Real，1955年10月26日－），西班牙刑事法院法官。以调查佛朗哥统治时期及西班牙内战时所犯下的暴行而闻名，2010年4月7日，他被最高
劳伦斯·达雷尔劳伦斯·达雷尔（英语：Lawrence Durrell，1912年2月27日－1990年11月7日）英国海外小说家、剧作家、诗人、旅行作家。生于英属印度贾朗达尔，逝于法国。代表作《亚历山大四重奏（英语：The
法老的诅咒法老的诅咒（英语：Curse of the pharaohs）是指针对任何打扰木乃伊的人的诅咒，据称会导致厄运、疾病甚至死亡。20世纪中叶以来，许多作家及纪录片认为“诅咒”的科学解释为细菌或辐
塞迈雷迪正则性引理数学上，塞迈雷迪正则性引理（Szemerédi regularity lemma）断言，给定任意一个足够大的图，都可以将其顶点集划分成若干个差不多一样大的子集，使得几乎每两个不同的子集之间的边，都具