algorithm - 分割树数据位置到树位置关系

Question

我想知道 data_array 数据位置与 tree_array 数据位置之间是否有任何关系。

int data[N];
int tree[M]; // lets M = 2^X-1, where X = nearest ceiling power of 2 to N;

void build_segment_tree();

我想知道我是否可以说 data[] 的第 n 个值映射到 tree[] 的第 i 个值。有什么数学上的解决办法吗？

Answer 1

当然可以。例如，线段树用于存储分部信息。

现在你会看到，如果你想用 N 个元素创建一个线段树，那么您将需要 ceil(log_2(N))+1 级别。在最后一层你会发现所有1 长度范围或单个元素。

这些元素会恰好在位置(1-index) 2^ceil(log_2(N)) 到 2^ceil(log_2(N))+N-1.

          [1-8]
        /       \
     [1-4]     [5-8]
     /   \      /   \
    [1-2][3-4] [5-6][7-8]
    /\     /\     /\    /\
   [1][2] [3][4] [5][6] [7][8]

---

1-11
/   \
1-6 7-11
1-3 4-6 7-9 10-11
1-2 3 4-5 6 7-8 9 10 11
1 2   4 5   7 8

这个答案只对2元素幂的线段树有效。

但对于其他元素，这些元素不一定是有组织的。

所以对于 N 个不是 2 的幂的答案将是错误的。

在那种情况下，您找不到任何形式化规则。