글 읽기 - 세그먼트 트리 5% 런타임에러 ㅠㅠ 제발 잡아주세요.

mypower300 4년 전 0

5%에서 자꾸 런타임에러가 납니다 ㅜㅜ 질문검색에 나와있는 테스트케이스도 모두 해보고, long long으로 확인도 해보고, 배열 크기도 충분히 크게 줬는데 뭐가 문제인지를 도무지 모르겠네요 ㅠㅠㅠㅠ 고수님들 부탁드립니다!

#include <iostream>

using namespace std;

long long root[4000000]; // 세그먼트 트리 구축(최대 리프 100만 기준 계산)

int tree_size = 0;
int tree_len = 0;
long long ans = 0;
int N, K, M;

void addleaf(long long, int, int, int, int);
long long complete_seg(int, int, int);
long long modify_tree(long long, int, int, int, int);
void sum_segment(int, int, int, int, int);

int main() {
	cin >> N >> M >> K;
	while ((1 << tree_size) < N) {
		tree_size++;
	}
	tree_len = 1 << tree_size;
	tree_size = ((1 << tree_size) * 2) - 1; // root[1] ~ root[size]까지 완전 이진트리 사용
	long long tmp;
	for (int i = 1; i <= N; i++) {
		cin >> tmp;
		addleaf(tmp, 1, tree_len, 1, i);
	}
	for (int i = N + 1; i <= tree_len; i++) addleaf(0, 1, tree_len, 1, i);
	complete_seg(1, tree_len, 1);
	long long input1, input2, input3;
	for (int i = 0; i < (K + M); i++) {
		cin >> input1 >> input2 >> input3;
		if (input1 == 1) { // 값 변환
			modify_tree(input3, 1, tree_len, 1, input2);
		}
		else { // 구간 출력
			ans = 0;
			sum_segment(1, tree_len, 1, input2, input3);
			cout << ans << endl;
		}
	}
	/*
	// 세그먼트 트리 출력
	int print = 1;
	int idx = 1;
	while (idx <= tree_size) {
		for (int i = 0; i < print; i++) {
			cout << root[idx].data << '\t';
			idx++;
		}
		cout << endl;
		print = print * 2;
	}
	*/
	return 1;
}
void sum_segment(int l, int r, int idx, int start, int end) {
	if (idx > tree_size) return;
	if (start > r || end < l) {
		return;
	}
	if (start <= l && r <= end) { // 현재 합칠 범위 안에 있는 경우
		ans += root[idx];
		return;
	}
	int m = (l + r) / 2;
	sum_segment(l, m, idx*2, start, end);
	sum_segment(m + 1, r, (idx*2) + 1, start, end);
}
long long modify_tree(long long key, int l, int r, int idx, int leaf) {
	long long value = 0;
	if (idx > tree_size) return value;
	if (l == leaf && r == leaf) {
		value = root[idx];
		root[idx] = key;
		return key - value;
	}
	int m = (l + r) / 2;
	if (leaf <= m) value = modify_tree(key, l, m, idx * 2, leaf);
	else value = modify_tree(key, m + 1, r, (idx * 2) + 1, leaf);
	root[idx] += value;
	return value;
}
void addleaf(long long key, int l, int r, int idx, int leaf) {
	if (idx > tree_size) return;
	if (l == leaf && r == leaf) {
		root[idx] = key;
		return;
	}
	int m = (l + r) / 2;
	if(leaf <= m) addleaf(key, l, m, idx * 2, leaf);
	else addleaf(key, m + 1, r, (idx * 2) + 1, leaf);
}

long long complete_seg(int l, int r, int idx) {
	long long tmp = 0;
	if (idx > tree_size) return tmp;
	if (l == r) {
		return root[idx];
	}
	int m = (l + r) / 2;
	long long tmpl = complete_seg(l, m, idx * 2);
	long long tmpr = complete_seg(m + 1, r, (idx * 2) + 1);
	root[idx] = tmpl + tmpr;
	return root[idx];
}

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

문제

문제

출처

ICPC

세그먼트 트리 5% 런타임에러 ㅠㅠ 제발 잡아주세요.

mypower300 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말