线段树

✍ dations ◷ 2025-12-10 21:34:25 #数据结构

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

相关

关节积血关节积血（英语：Hemarthrosis）是指关节内出血。这是血友病的常见症状。通常在损害受伤后发生，但主要在有出血倾向的患者，例如，使用华法林（warfarin，或其他抗凝剂）的患者和血友病患者。
反激动剂反激动剂（英语：inverse agonist）在药理学中是指和激动剂结合在相同的受体上，但引起相反的药理反应的物质。根据定义，反激动剂的效能为负。能受反激动剂作用的受体在没有结合任何
路易八世路易八世（狮子）（法语：Louis VIII le Lion，1187年9月5日－1226年11月8日），法兰西卡佩王朝国王（1223年—1226年在位），且在1216年—1217年要求英格兰王位。他生于巴黎，是法兰西国王腓力二世
奥匈帝国皇储奥托奥托·冯·哈布斯堡(Otto von Habsburg，1912年11月20日－2011年7月4日)，全名是弗兰茨·约瑟夫·奥托·罗伯特·玛丽亚·安东·卡尔·马克斯·海因里希·西克斯图斯·克萨韦尔·
阿尔卑斯交响曲阿尔卑斯交响曲（德语：Eine Alpensinfonie），作品64，是作曲家理查德·施特劳斯的最后一首交响诗。这首交响诗是献给当时的德累斯顿国家乐团。虽然作曲家标示这首乐曲为“交响曲”，但
唐正东唐正东（1982年9月14日－），江苏苏州人，中国篮球运动员。唐1995年开始接受正规篮球训练，后进入江苏南钢篮球俱乐部效力至今，司职中锋，多次入选中国国家男子篮球队，并曾当选为2004-2005赛
引擎 (消歧义)引擎为英语Engine的音译，即发动机或称作原动机。原指把能量转为动力的设备。引擎一词的含义延伸为做某件事的基本器具或固定机制。也引申为互联网或程序设计上的一种应用程序
曼努埃尔·德·奥利维拉曼诺·关狄多·品托·迪·奥利维拉（葡萄牙语：Manoel Cândido Pinto de Oliveira，1908年12月11日－2015年4月2日）是一位葡萄牙电影导演与编剧。他是电影史上唯一一位横跨无声电影
毒玫瑰《毒玫瑰》（英语：）是一部2019年美国惊悚片，由约翰·屈伏塔和摩根·费里曼主演。本片由乔治·葛罗（英语：George Gallo）执导，理查德·萨尔瓦托雷、法兰西斯·柯琴柯曼尼和卢卡·吉利波
李世熺李世熺，又称懿宁公主，是朝鲜王朝野史中记载的一位公主。根据1873年徐有英所著的《锦溪笔谈》的说法，李世熺是朝鲜世祖与贞熹王后尹氏所生的长女。癸酉靖难之后，世祖将朝鲜端宗流