2

我正在从这个页面学习段树：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)？

4

1 回答 1

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

数组“节点树[...]”存储树的所有节点。它的元素类型是“结构节点”。

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

它为存储在索引根目录中的结构节点调用拆分，将拆分节点的子节点的节点传递给它。它对 tree[root] 的实际作用取决于“拆分”的实现。

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 );
}
于 2014-01-26T08:22:09.080 回答