Segment tree data position to tree position relation

Question

I wonder if there is any relation between data_array data position to tree_array data position.

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

void build_segment_tree();

I wonder if I can say n'th value of data[] is mapped with i'th value of tree[]. is there any mathematical resolution?

Answer 1

You certainly can. For example segment tree is used for it's capapbility to store segment information.

Now you will see that if you want to create a segment tree out of N elements then you will need ceil(log_2(N))+1 levels. And in the last level you will find all the 1 length-range or the single elements.

These elements will be precisely in the position (1-index) 2^ceil(log_2(N)) to 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

This answer is for only valid for segment tree of power of 2 elements.

But for other elements the elements are not necessarily organized.

So the answer will be false for N those are not power of 2.

On that case you can't find any formualitve rule.