글 읽기 - tree에 값이 안들어 갑니다.

moon7392 5년 전 0

안녕하세요 구간 합 만들기 풀이 도중

세그먼트 트리 만들었는데 트리를 만드는 과정에서 10,11번 라인에 tree[index]에 값을 넣는 과정에서 값이 제대로 들어가지가 않습니다. 디버깅으로 계속 확인하고 다른 부분역시 세그먼트 트리를 공부하며 계속 확인했지만 도저히 원인을 모르겠습니다. tree[index]에 값이 제대로 들어가지 않고 이로인해 정확한 결과가 나오지 않는데 원인이 무엇일까요? ㅠㅠㅠ

#include <iostream>
#include <cmath>
using namespace std;

long long Nodes[1000000];
long long *tree;
long long make_tree(int s,int e,int index) {
	long long data;
	if (s == e) {
		data = Nodes[e];
		tree[index] = data;
	}

	else
		tree[index]=make_tree(s, (s+e) / 2, index * 2) + make_tree((s+e) / 2 + 1, e,  index * 2 + 1);	//index 1부터 시작
	return tree[index];
}

void update(int s, int e, long long value, int point, int index) {

	if (s > point || point > e)
		return;

	tree[index] += value;
	if (s != e)
	{
		update(s, (s+e) / 2,  value, point, index * 2);
		update((s+e) / 2 + 1, e,  value, point, index * 2 + 1);
	}
}
long long sum(int s, int e, int s_s, int s_e, int index) {
	if (s_s > e || s_e < s)
		return 0;
	
	else if (s_s <= s && e <= s_e) {
		return tree[index];
	}
	else{
		return sum(s, (s+e) / 2, s_s, s_e,index * 2)+sum((s+e) / 2 + 1, e, s_s, s_e, index * 2 + 1);
	}
}
int main(void)
{
	cin.tie(0);
	cout.tie(0);
	int N, M, K,flag,buf3,buf4;
	cin >> N>>M>> K;
//	Nodes = new long long[N];
	//long long* tree;
	//cout << (int)pow(2, ceil(log2(N)) + 2) + 1 << endl;
	tree = new long long[(int)pow(2, ceil(log2(N)) + 2)];

	long long buf,buf2,answer;
	for (int i = 0; i < N; i++)
	{
		cin >> buf;
		Nodes[i]=buf;
	}
	make_tree(0, N - 1,  1);

	for (int i = 0; i < M + K; i++)
	{

		cin >> flag;
		//answer = 0;
		if (flag == 1)
		{
			long long dif;
			cin >> buf3 >> buf2;
			dif = buf2-tree[buf3-1];
			Nodes[buf3 - 1] = buf2;
			update(0, N - 1, dif, buf3-1, 1);
		}
		else
		{
			cin >> buf3 >> buf4;
			cout<<sum(0, N - 1, buf3-1, buf4-1,1)<<"\n";
		}
	}
	return 0;
}

djm03178 5년 전 1

70번째 줄이 tree[buf3-1]이 아니라 Nodes[buf3-1]이어야 합니다. 이것만 고치면 맞습니다.

moon7392 5년 전 0

감사합니다... 저기에 문제가있었네요 답답함이 풀렸습니다 감사합니다!!

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

문제

문제

출처

ICPC

tree에 값이 안들어 갑니다.

moon7392 5년 전 0

djm03178 5년 전 1

moon7392 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말