我正在从这个页面学习线段树: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);
}
另外我应该在主函数中写什么才能使这个东西工作? 假设我有一个数组 A={2,3,2,4,20394,21,-132,2832} ,我如何使用此代码找到 RMQ(1,4)?
最佳答案
1.What will the split function do here ?
Nothing:函数体为空。可能还有一些其他需要执行操作的实现。 (参见示例 3)并参见 2b 的答案
2.... Where the value will be saved?
在调用“merge”的类/结构的“val”字段中。
1b.What is the use of the array tree and what values will be kept there ?
数组“node tree[...]”存储树的所有节点。它的元素类型是“结构节点”。
2b.What will this statement : tree[root].split(tree[left_child], tree[right_child]); do ?
它为存储在索引根的结构节点调用 split,并将拆分节点的子节点的节点传递给它。它对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)并不是您所期望的易于使用的接口(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 );
}
关于c++ - 线段树的实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21360682/