글 읽기 - 세그먼트 트리 반복문으로 구현

lim551 5년 전 0

이런 코드를 봤는데 query에서 어떻게 재귀를 반복문으로 바꿨는지 이해가 안 갑니다. 홀수 짝수가 왜 나오며 ++s, ++e는 왜 하는지..

2로 나누는거는 부모로 가는건 알겠는데 위 두개가 왜 그런지 모르겠네요

const int ST_MAX = 1 << 21, INF = 0x7fffffff;
struct segtree {
	int tree[ST_MAX], leaf;
	void construct(vi& ar) {
		fill(tree, tree + ST_MAX, INF);
		leaf = ST_MAX / 2;
		FOR(i, 0, ar.size()) tree[leaf+i] = ar[i];
		RFOR(i, leaf-1, 1) tree[i] = min(tree[i*2], tree[i*2+1]);
	}
	void update(int s, int k) {
		s += leaf;
		tree[s] = k;
		while(s > 0) {
			s /= 2;
			tree[s] = min(tree[s], k);
		}
	}
	int query(int s, int e) { return query2(s + leaf, e + leaf - 1); }
	int query2(int s, int e) {
		int ret = INF;
		while(s <= e) {
			if(s == e) return ret = min(ret, tree[s]);
			if(s % 2 == 1) ret = min(ret, tree[s]), ++s;
			if(e % 2 == 0) ret = min(ret, tree[e]), --e;
			s /= 2, e /= 2;
		}
		return ret;
	}
};

jh05013 5년 전 0

http://codeforces.com/blog/ent...

lim551 5년 전 0

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

세그먼트 트리 반복문으로 구현

lim551 5년 전 0

jh05013 5년 전 0

lim551 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말