글 읽기 - 세그먼트트리 사용했고, 시간초과 관련 질문이 있습니다.

muscj7 5년 전 1

우선 결과적으론 시간초과가 나옵니다.

이 문제를 풀기위해 세그먼트 트리를 처음 공부해서 활용해봤습니다.

아직 미숙하다고 생각이들긴 했지만 최대한 효율적이게 풀어보려고 했습니다.

각 함수는 다음과 같이 구성되어있습니다.

(1) 세그먼트 트리 구성 -> 2N

(2) 세그먼트 트리 리프노드 변경 -> Log(2N)

(3) 세그먼트 트리 탐색을 통한 구간 합 구하기 -> Log(2N) ~ Log(2N)*N

직관적으론 (3)의 함수가 걸림돌일거라는 생각이 드는데 도저히 방법이 생각이 안납니다.

#include <stdio.h>
using namespace std;

const int MAX = 1e6;

int N, M, K, answer = 0;
int nums[MAX];
int tree[2 * MAX];

// 세그먼트 트리 구성 : 대략 2N 탐색
int initTree(int s, int e, int idx) {
	if (s == e) {
		tree[idx] = nums[s - 1];
		return tree[idx];
	}
	else {
		tree[idx] = initTree(s, (s + e) / 2, idx * 2) + initTree((s + e) / 2 + 1, e, idx * 2 + 1);
		return tree[idx];
	}
}

// 세그먼트 트리 갱신 : 대략 Log(2N) 탐색
int editTree(int s, int e, int now_idx, int edit_idx, int newVal) {
	if (s == e) {
		if (edit_idx == s) {
			tree[now_idx] = newVal;
			return tree[now_idx];
		}
	}
	else {
		if (edit_idx >= s && edit_idx <= (s + e) / 2) 
			tree[now_idx] = editTree(s, (s + e) / 2, now_idx * 2, edit_idx, newVal) + tree[now_idx * 2 + 1];
		else if (edit_idx >= (s + e) / 2 + 1 && edit_idx <= e) 
			tree[now_idx] = editTree((s + e) / 2 + 1, e, now_idx * 2 + 1, edit_idx, newVal) + tree[now_idx * 2];
		return tree[now_idx];
	}
}

// 구간합 구하기 : 대략 Log(2N) ~ Log(2N)*N 탐색
void searchTree(int s, int e, int idx, int first, int last) {
	if (s == e) {
		// 값 변경 대상의 인덱스에 속하는가?
		if (s >= first && s <= last) {
			answer += tree[idx];
		}
	}
	else if (s == first && e == last) {
		answer += tree[idx];
	}
	else {
		if ((s + e) / 2 >= first)
			searchTree(s, (s + e) / 2, idx * 2, first, last);
		if ((s + e) / 2 + 1 <= last)
			searchTree((s + e) / 2 + 1, e, idx * 2 + 1, first, last);
	}
}

int main()
{
	// 입력
	scanf("%d %d %d", &N, &M, &K);
	int temp;
	for (int i = 0; i < N; i++) {
		scanf("%d", &temp);
		nums[i] = temp;
	}

	// 세그먼트 트리 구성
	initTree(1, N, 1);

	int t = M + K;
	while (t--) { // M+K번 수행
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		if (a == 1) {
			// 세그먼트 트리 수정
			editTree(1, N, 1, b, c);
		}
		else if (a == 2) {
			// [first ~ last]의 합 구하기
			searchTree(1, N, 1, b, c);
			printf("%d\n", answer);
			answer = 0;
		}
	}
	return 0;
}

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

문제

문제

출처

ICPC

세그먼트트리 사용했고, 시간초과 관련 질문이 있습니다.

muscj7 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말