为什么线段树是用数组而不是BT实现的
why segment tree is implemented using arrays instead of BT
我对线段树的实现有疑问。为什么线段树是用数组而不是二叉树来实现的？
如果我使用数组来实现它，我会得到什么好处？如果作为二叉树来实现，那么问题是什么？为了使用数组实现，我们需要将左子函数用作 2*i+1 并将右子函数用作 2*i+2.If 我们将其实现为二叉树，我们可以简单地执行 node -> lft & node->rht .但问题是什么？谢谢
优势是密度。数组占用的内容与 space 一样多。对于二叉树，每个节点都有内存管理开销。子指针也需要额外的 space。此外，数组通常位于连续的内存位置，而树节点可能分布在整个堆中，这意味着内存缓存不太可能提供帮助。
表示为数组的另一个优点是我们有从 parents 到 children 以及从 children 到 parents 的链接。
我对线段树的实现有疑问。为什么线段树是用数组而不是二叉树来实现的？
如果我使用数组来实现它，我会得到什么好处？如果作为二叉树来实现，那么问题是什么？为了使用数组实现，我们需要将左子函数用作 2*i+1 并将右子函数用作 2*i+2.If 我们将其实现为二叉树，我们可以简单地执行 node -> lft & node->rht .但问题是什么？谢谢
优势是密度。数组占用的内容与 space 一样多。对于二叉树，每个节点都有内存管理开销。子指针也需要额外的 space。此外，数组通常位于连续的内存位置，而树节点可能分布在整个堆中，这意味着内存缓存不太可能提供帮助。
表示为数组的另一个优点是我们有从 parents 到 children 以及从 children 到 parents 的链接。