我一直在尝试理解范围树一段时间,但我仍然不能理解它。
谁能给我解释一个实现,因为我想用它来解决二维RMQ,我知道段树,我的老师告诉我范围树类似于二维段树,但我就是想不出空间复杂度怎么能像二维段树一样小于n^2。
我不确定,但这是真的吗?它就像归并排序,所以使用向量
的内存将小于n^2void 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]);
}
谢谢:)
你检查过普通的饼干罐了吗?
比如维基百科,我在谷歌上找到的一个以前的几个讲座,还有一个堆栈问题?
我在大学时没有机会学习它,但它似乎是一个有趣的数据结构。