线段树

✍ dations ◷ 2025-12-05 18:09:30 #数据结构

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

相关

控制污染物排放政策控制污染物排放政策是国家制定的，用以强制污染者减少污染物排放的政策，现在国际通用的制定政策的原则是污染者付费原则。控制污染物排放政策的制定大体经历三个阶段：在最初阶段
特洛伊木马 (电脑)特洛伊木马（Trojan Horse）常被简称木马，在计算机领域中指的是一种后门程序，是黑客用来盗取其他用户的个人信息，甚至是远程控制对方的计算机而加壳制作，然后通过各种手段传播或者骗
大陆岛大陆岛指的是其地质构造与邻近的大陆相似，原属大陆的一部分，由于地壳下沉或海水上升以至于其与大陆相隔成岛。按其形成的原因可分为构造岛（又可分成板块及非板块交界带两类）和冲
英式车裂英式车裂，也称吊剖分尸刑或挂拉分（英语：hanged, drawn and quartered），是英格兰公元1352年立法加入的酷刑，意在惩处男性叛国者，早在亨利三世的执政期间（1216年 – 1272年）就已有行刑
努尼瓦克岛努尼瓦克岛(Nunivak Island)，白令海中第二大岛，属美国阿拉斯加州，为一火山岛，位于育空河河口外，全岛面积4,226.78平方公里，均为针叶林覆盖，仅北部有一居民点Mekoryuk，人口210人（2000
玫瑰山玫瑰山（英语：Rose Hills）是位于美国加利福尼亚州洛杉矶县的一个人口普查指定地区。玫瑰山的座标为34°00′33″N 118°02′31″W / 34.00917°N 118.04194°W / 34.00917; -118
麦角酸麦角酸（lysergic acid 亦称：D-lysergic acid 及 (+)-lysergic acid）是寄生于禾本科植物的多种真菌（麦角）所产生的次级代谢产物，属于麦角毒素的一种，是迷幻药麦角二乙胺（LSD）的前趋物
皇家梅赫伦足球会皇家梅赫伦足球会（Y.R. K.V. Mechelen）是一家比利时的足球俱乐部。主场设在安特卫普省城市梅赫伦。俱乐部成立于1904年，在历史上曾经四次获得比利时足球甲级联赛的冠军。此外
柯博尔柯博尔（Colin Campbell）是一位互联网行业先驱、连续创业家，曾联合创办多家互联网和科技兴公司。他是.Club顶级域名公司（.Club Domains LLC）的创始人，目前担任董事长与首席执行官职
万骑万骑，极言骑兵之多。扬雄《长杨赋》:“罗千乘于林莽，列万骑于山隅。”