RMQ 자료구조 - Range Minimum/Maximum Query (Indexed Tree)

인덱스 트리(Indexed Tree)는 N개의 데이터를 사용하여 2N크기의 이진 트리를 생성하고 각 범위를 대표하는 값(최대, 최소, 누적합 등)을 이진트리 형태로 저장하여, 이후에 한 구간 [l, r]에 대한 대표값을 O(log2(N))만에 구할 수 있게 해주는 형태입니다.

인덱스 트리가 중요한 이유는 데이터가 갱신되어도 이 갱신된 결과를 반영하는 것이 O(log2(N))의 시간복잡도는 가지는 점이며, 이는 데이터를 단순히 배열으로 저장했을때와 가장 큰 차이가 됩니다.

#define vi vector<int>
#define mid (lm+rm)/2
#define LQR l, r, lm, mid, pos*2
#define RQR l, r, mid+1, rm, pos*2+1
 
struct IT{
        int lv, w;
        vi minv, maxv;
        //0-based
        void update( int pos,int val ){
                pos += w;
                minv[pos] = maxv[pos] = val;
                while(pos /= 2){
                        maxv[pos] = max(maxv[pos*2], maxv[pos*2+1]);
                        minv[pos] = min(minv[pos*2], minv[pos*2+1]);
                }
        }
        IT(int N ){
                for(lv=0, w=1;  w<N;  w*=2,lv++);
                minv = maxv = vi(w*2+1);
        }
        //사용법 : maxq(l,r)  단, [l,r ]은 0-based
        int maxq(int l, int r, int lm=0,int rm=0, int pos = 1){
                if(pos == 1) rm = w-1;
                if( r < lm || rm < l )  return -1e9;
                if( l <= lm && rm <= r )      return maxv[pos];
                return max( maxq(LQR), maxq(RQR));
        }
        int minq(int l, int r, int lm=0,int rm=0, int pos = 1){
                if(pos == 1) rm = w-1;
                if( r < lm || rm < l )  return 1e9;
                if( l <= lm && rm <= r )      return minv[pos];
                return min( minq(LQR), minq(RQR));
        }
};

https://edu.goorm.io/learn/lecture/554/알고리즘-문제해결기법-입문