[정올 1726] 구간의 최대값1

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=999&sca=99&sfl=wr_hit&stx=1726 

JUNGOL

/*
구간의 최대값
segment tree: 이진트리이며, 부모는 자식 2개중 큰 값을 가진다.
*/
#include <stdio.h>

const int LM = 50005;
const int TLM = 1 << 17; /// 131072

int N, Q, A[LM];
int tree[TLM]; //이진트리는 전체 크기의 2배이상

inline int max(int a, int b) { //#define 쓰지 마라
	return a > b ? a : b;
}
void build(int now, int s, int e) { //전체 배열 A가 주어질 때 가능, s, e는 A의 idx, 
	//now는 A[s]~A[e] 구간에서 가장 큰 값이 담기는 트리의 부모 idx
	if (s >= e) { //leaf node에 도달하면 트리노드에 A의 값을 넣음
		tree[now] = A[s]; 
		return;
	}
	int lch = now * 2, rch = lch + 1; //왼쪽 자식과 오른쪽 자식의 idx
	int m = (s + e) / 2; //비교할 배열 A의 중간값
	build(lch, s, m); //왼쪽 절반 구간을 채움
	build(rch, m + 1, e); //오른쪽 절반 구간을 채움
	tree[now] = max(tree[lch], tree[rch]); //두 자식 중에 큰 값만 저장하면, 내 구간의 최대값이 나옴
}

void update(int now, int s, int e, int tg, int val) {
	if (s == e) { //leaf node(개별원소)에 도달하면 값 업데이트
		tree[now] = val;
		return;
	}
	int lch = now * 2, rch = lch + 1; //왼쪽, 오른쪽 자식의 idx 구함
	int m = (s + e) / 2; //원본배열의 중간지점
	if (tg <= m) update(lch, s, m, tg, val); //찾고자 하는 원본 idx가 왼쪽 절반에 속하면, 왼쪽 절반을 탐색
	else update(rch, m + 1, e, tg, val);//오른쪽 절반에 속하면, 오른쪽 절반을 탐색
	tree[now] = max(tree[lch], tree[rch]);//업데이트 후 부모를 업데이트, 용도에 따라 다르게 적용
}

//s부터 e 안에서, si부터, ei까지의 최대값을 구한다.

int query(int now, int s, int e, int si, int ei) {
	if (si <= s && e <= ei) return tree[now]; // 1) 타겟 구간이 내 구간에 완전히 속한 경우
	if (e < si || ei < s) return 0; // 2) 타겟 구간이 내 구간을 완전히 벗어나는 경우
	int lch = now * 2, rch = lch + 1; // 3) 타겟 구간이 내 구간에 일부만 포함된 경우
	int m = (s + e) / 2; //해당 노드의 구간을 절반으로 쪼개서 
	int lv = query(lch, s, m, si, ei); // 왼쪽 절반을 탐색
	int rv = query(rch, m + 1, e, si, ei); // 오른쪽 절반을 탐색
	return max(lv, rv); //유효한 노드의 합 리턴
}

//max(lv, rv); //왼쪽 vs 오른쪽 최대값 중 큰 걸 리턴
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &N, &Q);
	int i, si, ei;
	for (i = 1; i <= N; ++i) scanf("%d", A + i);
	//build(1, 1, N);
	for (i = 1; i <= N; ++i) {
		update(1, 1, N, i, A[i]);
	}
	for (i = 0; i < Q; ++i) {
		scanf("%d %d", &si, &ei);
		printf("%d\n", query(1, 1, N, si, ei));
	}
	return 0;
}