实现2d范围树C++

Question

我一直在尝试理解范围树一段时间，但我仍然无法理解它。

有人可以解释给我一个实现，因为我想用它来解决2D RMQ，我知道段树，我的老师告诉我范围树类似于2D段树，但我不能想想空间复杂度如何能像二维分割树那样少于n^2。

我不知道这一点，但它是真实的，它就像归并排序，所以内存将小于n^2使用矢量

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

谢谢:)

Answer 1

有无你检查了通常的饼干罐？

如Wikipedia，我在Google上发现的几个former lecture，还有一个Stack Question？

我没有在大学学习它的乐趣，但它似乎是一个有趣的数据结构。