세그먼트트리 #level #2^l == 1<<l

세그먼트 트리를 공부했다.

펜윅트리도 공부하자!

#1. 최대값과 최소값

문제번호: 2357

분류: 세그먼트트리

N = 10, M = 4

            

                            1                               :level 0

 ...............................

  75      100     51      52       81       0       :level 3

75 30 100 38 50 51 52 20  81  5   0   0   0: level 4

 0   1   2   3   4   5   6   7   8   9    ...      15 : 데이터인덱스 (0 ~2^4-1)

10000 ...............................................11111 :어레이인덱스 (2^4 ~ 2^4+2^4-1)

1 10

3 5

6 9

8 10

코드

#include <stdio.h>

#include <vector>

#include <math.h>

#include <climits>

using namespace std;

int N, M;

int level;

int mtree[262144]; //2^18 = 262144 최소값 구간트리

int Mtree[262144]; //최대값 구간트리

int findMin(int x1, int x2) {

return (x1 > x2) ? x2 : x1;

}

int findMax(int x1, int x2) {

return (x1 < x2) ? x2 : x1;

}

int findSeg(int curL, int curR, int segL, int segR, int index, int Arr[], int(*func)(int,int)) {

if (curR < segL || segR < curL) {

if (func == findMin) return INT_MAX;

if (func == findMax) return INT_MIN;

}

if (segL <= curL && curR <= segR) return Arr[index];

int mid = (curL + curR) / 2;

return (*func)(findSeg(curL, mid, segL, segR, (index<<1) , Arr, func), findSeg(mid + 1, curR, segL, segR, (index <<1) + 1, Arr, func));

}

int findMSB(unsigned int n) {

int cnt = 0;

while (n) {

n >>= 1;

cnt++;

}

return cnt;

}

int main(void) {

freopen("Text.txt", "r", stdin);

scanf("%d %d", &N, &M);

level = findMSB(N); 

/*

Level 구성 : 0(root)~level(leaf), (총 level+1개)

각 level의 원소 개수: 2^level 개 (2^level == 1<<level)   ex. 0~1101(2)~1111(2) : 2^4=16개, level:4, 인덱스: 10000~11111 : 2^4+0~2^4+2^4-1

각 level의 인덱스 : 2^level+0 ~ 2^level+2^level+1

*/

int leaf_idx_start = (1 << level);

for (int i = 0; i < N; i++) {

int temp;

scanf("%d",&temp);

mtree[leaf_idx_start + i] = temp;

Mtree[leaf_idx_start + i] = temp;

}

for (int i = N; i < leaf_idx_start; i++) {

mtree[leaf_idx_start + i] = mtree[leaf_idx_start + N - 1];

Mtree[leaf_idx_start + i] = Mtree[leaf_idx_start + N - 1];

}

for(int l = level-1; l>=0; l--){

int node_idx_start = (1 << l);

for (int i = 0; i < (1 << l); i++) {

mtree[node_idx_start + i] = (mtree[(node_idx_start + i)<<1] < mtree[((node_idx_start + i)<<1)+1]) ? mtree[(node_idx_start + i)<<1] : mtree[((node_idx_start + i)<<1) + 1];

Mtree[node_idx_start + i] = (Mtree[(node_idx_start + i)<<1] > Mtree[((node_idx_start + i)<<1)+1]) ? Mtree[(node_idx_start + i)<<1] : Mtree[((node_idx_start + i)<<1) + 1];

}

}

for (int i = 1; i <= M; i++) {

int a, b;

scanf("%d %d", &a, &b);

int mVal, MVal;

mVal = findSeg(0, leaf_idx_start-1, a-1, b-1, 1, mtree, findMin);

MVal = findSeg(0, leaf_idx_start-1, a-1, b-1, 1, Mtree, findMax);

printf("%d %d\n", mVal, MVal);

}

return 0;

}