2 차원 범위 트리를 구현합니다. C++

Question

얼마 동안 범위 트리를 이해하려고 노력했지만 계속 이해할 수는 없습니다.

2D RMQ를 해결하기 위해 그것을 사용하고 싶기 때문에 누군가 구현에 대해 설명 할 수 있습니까? 선생님은 세그먼트 트리를 알고 선생님이 범위 트리가 2D 세그먼트 트리와 비슷하다고 말할 수는 있지만 그럴 수 없습니다. 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, former lecture과 Google에서 발견 한 Stack Question 등이 있습니까?

나는 대학에서 그것을 배우는 즐거움을 갖지 못했지만 흥미로운 데이터 구조 인 것처럼 보인다.