Сегмент реализации дерева

Question

я узнавал дерево сегмента с этой страницы: http://letuskode.blogspot.com/2013/01/segtrees.html

Я нахожу проблемы, чтобы понять различные фрагменты code.I задаст их по one.Any помощь будет оценена.

декларация Node:

struct node{ 
    int val; 
    void split(node& l, node& r){} 
    void merge(node& a, node& b) 
    { 
     val = min(a.val, b.val); 
    } 
}tree[1<<(n+1)]; 

1.Что будет функция сплит здесь делать?

2.Этот код используется для RMQ. Поэтому я думаю, что val будет минимальным из двух сегментов и сохранит его в другом сегменте. Где будет сохранено значение?

Диапазон запросов Функция:

node range_query(int root, int left_most_leaf, int right_most_leaf, int u, int v) 
{ 
    //query the interval [u,v), ie, {x:u<=x<v} 
    //the interval [left_most_leaf,right_most_leaf) is 
    //the set of all leaves descending from "root" 
    if(u<=left_most_leaf && right_most_leaf<=v) 
     return tree[root]; 
    int mid = (left_most_leaf+right_most_leaf)/2, 
     left_child = root*2, 
     right_child = left_child+1; 
    tree[root].split(tree[left_child], tree[right_child]); 
    //node l=identity, r=identity; 
    //identity is an element such that merge(x,identity) = merge(identity,x) = x for all x 
    if(u < mid) l = range_query(left_child, left_most_leaf, mid, u, v); 
    if(v > mid) r = range_query(right_child, mid, right_most_leaf, u, v); 
    tree[root].merge(tree[left_child],tree[right_child]); 
    node n; 
    n.merge(l,r); 
    return n; 
} 

1.Что является использование дерева массива и какие ценности будут храниться там?

2.Что будет это утверждение: дерево [корень] .split (дерево [left_child], tree [right_child]); делать ?

3.Что будут делать эти заявления? :

node n; 
n.merge(l,r); 
return n; 

Update и Merge Up функции: Я не понимая эти две функции должным образом:

void mergeup(int postn) 
{ 
    postn >>=1; 
    while(postn>0) 
    { 
     tree[postn].merge(tree[postn*2],tree[postn*2+1]); 
     postn >>=1; 
    } 
} 
void update(int pos, node new_val) 
{ 
    pos+=(1<<n); 
    tree[pos]=new_val; 
    mergeup(pos); 
} 

Кроме того, что я должен написать внутри основной функции, чтобы сделать эту работу вещь? Предположим, у меня есть массив A = {2,3,2,4,20394,21, -132,2832}, как я могу использовать этот код для поиска RMQ (1,4)?

Answer 1

1.What will the split function do here ? 

Ничего: корпус функции пуст. Там может быть какая-то другая реализация, в которой требуется действие. (Смотри пример 3) и видим ответ на 2b

2.... Where the value will be saved? 

В поле «VAL» из класса/структуры, для которых «Объединить» называется.

1b.What is the use of the array tree and what values will be kept there ? 

Array "tree tree [...]" хранит все узлы дерева. Его тип элемента - «узел структуры».

2b.What will this statement : tree[root].split(tree[left_child], tree[right_child]); do ? 

Он вызывает раскол для узла структуры, который хранится в индексном корне, минуя узлы детей Раскола узла к нему. То, что это на самом деле делает с деревом [root], зависит от реализации «split».

3b.What will those statements do ? : 

node n;   // declare a new node 
n.merge(l,r); // call merge - store the minimum of l.val, r.val into n.val 
return n;  // terminate the function and return n 

Мне нужно выяснить ответы на ваши последние вопросы в контексте этого кода. Понадобится немного времени.

Позже Это должно построить дерево и выполнить запрос диапазона. Я не уверен, что код на этой странице правильный. В любом случае, интерфейс для range_query - это не то, что вы ожидаете от простого использования.

int main(){ 
    int a[] = { -132, 1, 2, 3, 4, 21, 2832, 20394}; 
    for(int i = 0; i < 8; i++){ 
    node x; 
    x.val = a[i]; 
    update(i, x); 
    } 

    node y = range_query(0, 8, 15, 8 + 1, 8 + 4); 
}