线段树

✍ dations ◷ 2025-12-03 23:09:44 #数据结构

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

相关

合成按照IUPAC金皮书的定义，不对称合成（enantioselective synthesis、asymmetric synthesis），也称手性合成、立体选择性合成、对映选择性合成，是研究向反应物引入一个或多个具手性元
三硬脂酸甘油酯硬脂精是甘油的三硬脂酸酯类，为动物脂肪的组成成分之一。也叫硬脂酸甘油酯或三硬脂酸甘油酯。无色无味无臭结晶或粉末。不溶于水、乙醚和里格罗因（ligroin），溶于乙醇、氯仿、二
物理常数物理常数，或称物理定数、物理常量或自然常数，指的是物理学中数值固定不变的物理量。它与数学常数不同，数学常数指的是一个在数值上固定不变的值，但是这个值不一定与物理测量有关
羟基化反应羟基化（法语：Hydroxylation，也称羟化）是向分子引入羟基（－OH）的过程。常指用羟基取代碳上的氢原子（－H）的反应。产物是醇、酚等。生化中，催化羟化反应的酶称为羟化酶。←氨基酸二级结构→
程序记忆内隐记忆（implicit memory），又称为程序记忆（procedural memory），一种长期记忆的形式，指关于技术、过程、或“如何做”的记忆。记忆有时候会被贮存在程序记忆（procedural memory）中，当
洮儿河洮儿河位于中国东北地区，是嫩江右岸的一条重要支流。洮儿河发源于内蒙古自治区科右前旗大兴安岭主峰索岳尔济山麓，流经内蒙古自治区兴安盟和吉林省西北部，在吉林省大安市月亮泡
结构模体结构模体（英语：structural motif，亦称为结构基序）是链状生物分子（如蛋白质或核酸）中的一种超二级结构，也存在于其它分子之中。结构模体使得我们无法预测蛋白的生物学功能：不同蛋白质
柯特克·安吉玛-托卡柯特克·阿米尔比托夫纳·安吉玛-托卡（Khertek Amyrbitovna Anchimaa-Toka，俄语：Хертек Амырбитовна Анчимаа-Тока，图瓦语：Анчимаа-Тока
塞巴斯蒂安·康拉德塞巴斯蒂安·康拉德（德语：Sebastian Conrad，1966年－）是一名德国历史学家，专攻全球史、殖民史、史学史和东亚研究，2010年起担任柏林自由大学新历史教授。康拉德出生于西德海德堡，曾就
碘化铵碘化铵（英文：Ammonium iodide），化学式为NH4I。常温下呈无色结晶或颗粒。可溶于水、醋酸、氨，易溶于乙醇、丙酮；微溶于乙醚。碘化铵加热后升华，其气体遇光及空气会出现游离碘而呈黄