[C++] 구간트리 (Binary Indexed Tree) - 구간 최대,최소값

struct IndexedTree {

   vector<int> tree;

   int size;

   IndexedTree(int n, int *arr) :

          tree(4 * n, 987654321) {   //넉넉하게 4*n 사이즈 배열 생성, 초기값 지정

       size = 1;

       while (size < n) //2의 배수로 최저 깊이레벨 노드 개수 결정

          size *= 2;

       for (int i = 0; i < n; i++)

          tree[size + i] = arr[i];   //값 복사

       init(1);  //값들 다 계산.

   }

   /* 후라이빗 함수 */

   int init(int pos) {

       if (pos >= size) //단말 노드일 경우

          return tree[pos];

       return tree[pos] = min(init(pos * 2), init(pos * 2 + 1));

   }

   int query(int left, int right, int node, int nodeLeft, int nodeRight) {

       left = max(left, nodeLeft);

       right = min(right, nodeRight);

       if (left > right)

          return 987654321;   //초기값

       if (left == nodeLeft && right == nodeRight)

          return tree[node];

       int mid = (nodeLeft + nodeRight) / 2;

       return min(query(left, right, node * 2, nodeLeft, mid),

              query(left, right, node * 2 + 1, mid + 1, nodeRight));

   }

 

   void update(int pos) {

       if (pos < 1)

          return;   //루트까지만

       tree[pos] = min(tree[pos * 2], tree[pos * 2 + 1]);   //갱신

       update(pos / 2);   //부모 노드 따라 계속 올라감

   }

 

   /* 사용시 직접 호출할 함수 */

   int query(int left, int right) {  //left~right 사이의 대표값

       return query(left, right, 1, 0, size - 1);

   }

   void update(int index, int newValue) {   //index번 노드 값을 갱신

       tree[size + index] = newValue; //해당 노드 업데이트

       update((size + index) / 2); //부모 노드 재귀 업데이트

   }

};

사용시 초기값(987654321)은 const 선언하거나 define 해서 사용하시면 됨니다.

구간 합만을 구하는 경우는 더 간단한 펜윅트리가 있습니다.(대신 초기화가 없습니다.. lgN 시간으로 되지 않는다는 말)

사용법

생성

int arr[10]={1,2,3,4,5,6,7,8,9,10};

이런 배열이 있으면

IndexedTree tree(10, arr);

이렇게 트리 생성. 그러면 배열의 값 모두 복사하고 그 외 값은 아주 큰 값으로 초기화 함.

구간 쿼리

query(5,8) 하면 5~8중 가장 작은 값 리턴.

값 갱신

update(4,30) 하면 4번 값을 30으로 갱신. 부모 재귀적으로 모두 갱신.

시간복잡도

쿼리,갱신 모두 O(lgN)

초기화 및 업데이트 부분은 자작인데 구간 쿼리 함수는 어려워서 참고 하였습니다. https://jmk.pe.kr/read/generic-segment-tree-using-templates

초기값을 바꾸고 min 비교를 max로 바꾸거나 합을 구하는 식으로 바꿔 구간 최대값이나 구간 합으로 쉽게 변경이 가능합니다.