Реализация дерева сегментов

Question

Реализация дерева сегментов

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

Я нахожу затруднения, чтобы понять различные фрагменты кода. Я буду спрашивать их один за другим. Любая помощь будет оценена.

Объявление узла:

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. Что будет с этим утверждением: tree [root] .split (tree [left_child], tree [right_child]); делать ?

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

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

Функции обновления и слияния:
Я не правильно понимаю эти две функции:

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)?

2

c++segment-tree

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

1.What will the split function do here ?

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

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

В поле «val» класса / структуры, для которых вызывается «merge».

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

Массив «узел дерева […]» хранит все узлы дерева. Его тип элемента — «структура узла».

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

Он вызывает split для узла структуры, который хранится в корневом каталоге индекса, передавая ему дочерние узлы узла split. Что он на самом деле делает с деревом [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 );
}

2