트리 위치 데이터와 트리 위치 관계

Question

data_array 데이터 위치와 tree_array 데이터 위치 사이에 관계가 있는지 궁금합니다. 나는 데이터의 n 번째 값 [] [] 나무의 i 번째 값으로 매핑되는 말을 할 수 있다면

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

void build_segment_tree(); 

이 궁금하다. 수학적 해결책이 있습니까?

Answer 1

할 수 있습니다. 예를 들어, 세그먼트 트리는 세그먼트 정보를 저장할 수있는 능력을 위해 사용됩니다 (예 : ).

개의 요소가있는 세그먼트 트리를 만들려면 레벨이 ceil(log_2(N))+1이어야합니다. 마지막 레벨에서는 길이 범위 또는 단일 요소를 모두 찾을 수 있습니다.

이러한 요소는 정확하게 (1- 색인) 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 

이 대답은 두 요소의 힘의 세그먼트 트리에 대해서만 유효입니다.

그러나 다른 요소의 경우 요소가 반드시 구성되어 있지는 않습니다.

그래서 대답은 사람들은 당신이 어떤 formualitve 규칙을 찾을 수없는 경우 2.

의 전력 아닌 N에 대한 잘못된 것입니다.