通过 
搜索
搜索martanlv / koki
PHP 数据结构和实用工具
v1.0.7
2018-02-13 06:24 UTC
Requires
- php: ^7.0
Requires (Dev)
- ivoba/dump-die-shortcuts: ^1.0
- phpunit/phpunit: ^6.5
This package is not auto-updated.
Last update: 2024-09-28 11:48:17 UTC
README
区间树：其想法是对自平衡二叉搜索树（BST）如红黑树、AVL树等进行增强，以便维护一组区间，使得所有操作都可以在 O(Logn) 时间内完成。
待办事项
- ***段树 存储区间，并针对“这些区间中哪个包含给定点”的查询进行了优化。
- 区间树 也存储区间，但针对“这些区间中哪个与给定区间重叠”的查询进行了优化。它也可以用于点查询 - 与段树类似。
- 范围树存储点，并针对“哪些点落在给定区间内”的查询进行了优化。
- 二叉索引树 存储每个索引的项目计数，并针对“索引 m 和 n 之间有多少个项目”的查询进行了优化。
一维性能/空间消耗
- 段树 - O(n logn) 预处理时间，O(k+logn) 查询时间，O(n logn) 空间
- 区间树 - O(n logn) 预处理时间，O(k+logn) 查询时间，O(n) 空间
- 范围树 - O(n logn) 预处理时间，O(k+logn) 查询时间，O(n) 空间
- 二叉索引树 - O(n logn) 预处理时间，O(logn) 查询时间，O(n) 空间（k 是报告的结果数量）。
所有数据结构都可以是动态的，这意味着使用场景包括数据更改和查询
- 段树 - 区间可以以 O(logn) 的时间添加/删除（见此处）
- 区间树 - 区间可以以 O(logn) 的时间添加/删除
- 范围树 - 可以以 O(logn) 的时间添加/删除新点（见此处）
- 二叉索引树 - 每个索引的项目计数可以以 O(logn) 的时间增加
高维（d>1）
- 段树 - O(n(logn)^d) 预处理时间，O(k+(logn)^d) 查询时间，O(n(logn)^(d-1)) 空间
- 区间树 - O(n logn) 预处理时间，O(k+(logn)^d) 查询时间，O(n logn) 空间
- 范围树 - O(n(logn)^d) 预处理时间，O(k+(logn)^d) 查询时间，O(n(logn)^(d-1))) 空间
- 二叉索引树 - O(n(logn)^d) 预处理时间，O((logn)^d) 查询时间，O(n(logn)^d) 空间
贝多芬同意。
--
__