实现2d范围树c ++ [英] implement 2d range tree c++
问题描述
有人可以用一个实现来解释这个问题,因为我想使用它来解决2D RMQ,我知道段树,我的老师告诉我范围树是类似于2d段树,但我只是不能认为如何空间复杂度可以小于n ^ 2像2d段树。
我不知道这是什么,但它是真的,它像合并排序,所以内存将小于n ^ 2使用向量
void merge(vector< int>& res,vector< int>& a,vector< int& b $ b {
int la = 0;
int lb = 0;
int sa = SIZE(a);
int sb = SIZE(b);
while(la {
if(la> = sa){res.pb(b [lb]); lb ++;}
else if(lb> = sb){res.pb(a [la]); la ++;}
else
{
if ]){res.pb(a [la]); la ++;}
else {res.pb(b [lb]); lb ++;}
}
}
}
void build(int n,int l,int r)
{
if(l == r)
{
rtree [n]。 pb(ar [1]);
return;
}
int m =(l + r)/ 2;
build(2 * n,l,m);
build(2 * n + 1,m + 1,r)
merge(rtree [n],rtree [2 * n],rtree [2 * n + 1]);感谢:)
例如 org / wiki / Range_treerel =nofollow>维基百科,我在Google上发现的几个我之前的讲座,以及堆栈问题?
我没有在大学学习的乐趣,但它似乎是一个有趣的数据结构。
I have been trying to understand range tree for some time, but i still can't understand it.
Can someone explain it to me with an implementation, because i want to use it to solve 2D RMQ, i know segment tree, and my teacher tell me range tree is similar to 2d segment tree, but i just can't think how the space complexity can be less than n^2 like 2d segment tree.
I'm not sure about this, but is it true that, it's like merge sort, so the memory will be less than n^2 using vector
void merge(vector<int> &res,vector<int> &a,vector<int> &b)
{
int la = 0;
int lb = 0;
int sa = SIZE(a);
int sb = SIZE(b);
while(la < sa || lb < sb)
{
if (la >= sa) {res.pb(b[lb]);lb++;}
else if (lb >= sb) {res.pb(a[la]);la++;}
else
{
if (a[la] < b[lb]) {res.pb(a[la]);la++;}
else {res.pb(b[lb]);lb++;}
}
}
}
void build(int n,int l,int r)
{
if (l == r)
{
rtree[n].pb(ar[l]);
return;
}
int m = (l+r)/2;
build(2*n,l,m);
build(2*n+1,m+1,r);
merge(rtree[n],rtree[2*n],rtree[2*n+1]);
}
Thanks :)
解决方案 Have you checked the usual cookie jars?
Such as Wikipedia, a former lecture of several I found on Google and in addition to a Stack Question?
I did not have the pleasure of learning it at University but it appears to be an interesting data structure.
这篇关于实现2d范围树c ++的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文