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

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 长度范围或单个元素。

这些元素将恰好位于 2^ceil(log_2(N)) 到 2^ceil(log_2(N))+N-1 的 (1-index) 位置。

          [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 的幂的答案将为假。

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

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

Segment tree data position to tree position relation

algorithm

binary-tree

divide-and-conquer