为什么使用数组而不是BT实现分段树

Question

我对分段树实现有疑问。为什么使用数组而不是二叉树实现分段树？

如果我使用数组实现它，我会得到什么好处，如果作为二叉树实现，那么是什么问题？为了实现使用数组，我们需要使用左侧子函数作为2 * i + 1，右侧子函数作为2 * i + 2。如果我们实现为二叉树，我们可以简单地执行node-> lft & node-> rht。但是问题是什么？谢谢

Answer 1

优点是密度。一个数组需要的空间与内容大致相同。对于二叉树，每个节点都有内存管理开销。孩子指针也需要额外的空间。此外，数组通常位于连续的内存位置，而树节点可能遍布整个堆，这意味着内存缓存不太可能提供帮助。