структура — реализовать 2-мерное дерево диапазона Переполнение стека

Я пытался понять дерево диапазонов в течение некоторого времени, но я все еще не могу понять это.

Может кто-нибудь объяснить мне это с помощью реализации, потому что я хочу использовать это для решения 2D RMQ, я знаю дерево сегментов, и мой учитель сказал мне, что дерево диапазонов похоже на дерево 2D сегментов, но я просто не могу понять, как пространство сложность может быть меньше, чем n ^ 2, как 2d сегментного дерева.

Я не уверен в этом, но правда ли, что это похоже на сортировку слиянием, поэтому память будет меньше 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]);
}

Спасибо 🙂