c++ - 线段树实现

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.split函数在这里做什么？

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);
}

此外，我应该在 main 函数中写些什么才能使它正常工作？假设我有一个数组 A={2,3,2,4,20394,21,-132,2832} ，我如何使用这段代码找到 RMQ(1,4)？

Answer 1

1.What will the split function do here ?

Nothing:函数体是空的。可能还有其他一些需要执行操作的实现。 (参见示例 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 ?

数组“node tree[...]”存储了树的所有节点。它的元素类型是“struct node”。

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

它为存储在索引根中的结构节点调用拆分，将拆分节点的子节点传递给它。它对 tree[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 的接口(interface)并不是您期望的那样易于使用。

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 );
}