인덱스트리(Indexed Tree)

어떤 구간의 최대,최소를 O(lgN)에 알게 해주는 자료구조 

정의되는 연산

1.) 원소값 갱신

2.) a~b의 최대 또는 최소값 반환

완전이진트리를 배열로 구현

 ( 들어갈 원소 숫자만큼의 단말노드를 가질 수 있도록 크기를 조정 , 편의상 그냥 4 * N으로 잡으면 된다. 값은 단말노드를 통해서만 들어간다.

               예 : 들어갈 원소가 9개라고 한다면 최소한 단말노드가 9개

                     여야 하므로 비단말노드 15개, 단말노드 16개를 가지는

                     완전이진트리 형태가 되어야 할것이다.  )

원소값 갱신: 원소가 하나 추가될때마다 부모노드와 비교하여 최대, 최소 ( 또는 다른 그 구간을 대표할만한)을 갱신한다.

a~b의 최대,최소 반환: a (왼쪽끝 노드)에 있는 노드가 오른쪽노드일때 그 부모노드가 구간을 대표하는 값을 가질 수 없다는점을 이용하여 노드의 위치가 오른쪽일때는 그 오른쪽에 에 위치하는 왼쪽노드  (이 두 노드는 서로 다른 부모노드를 가진다.) 로, 왼쪽노드일때는 부모노드로 위치를 옮겨가면서 리턴값을 갱신한다. 반대로 b(오른쪽끝 노드) 노드는 왼쪽노드일때 그 노드의 왼쪽에 있는 오른쪽노드, 오른쪽 노드일때 그 부모노드로 위치를 옮겨가면서 리턴값을 갱신한다. 두 위치가 교차되거나 겹칠때 루프를 종료한다.

const int INF = 2e9;
struct Tree{
    int first;
    vector<int> tree;
    Tree(int n)
    {
        for(first=1;first<n;first<<=1);
        tree = vector<int>( n<<2, INF);
    }

    void update(int pos, int val)
    {
        pos += first;
        tree[pos] = val;
        while(pos>>1){
            tree[pos>>1] = min(tree[pos>>1],tree[pos]);
            pos>>=1;
        }
    }

    int query(int l, int r)
    {
        l += first;
        r += first;
        int ret = INF;
        while(l<=r){
            ret = min(ret, min(tree[l],tree[r]));
            l = (l+1)>>1;
            r = (r-1)>>1;
        }
        return ret;
    }

};