글 읽기 - 틀린 곳을 찾아주세요(세그먼트 트리)

plan222 3년 전 0

루트 노드가 인덱스 0이고, init할 때 full binary tree를 만듭니다.

temp 는 리프노드의 시작 인덱스 입니다.

어디가 문제일까요??

#include <iostream>
#include<string>
#include<algorithm>
#include<vector>

#define MAX(A,B) A>B?A:B;
#define MIN(A,B) A<B?A:B;
using namespace std;

/*세그먼트 트리*/
struct sTree {
	int start;
	int end;
	long long value;
} stree[2100000]; //(요소 갯수x2-1) 보다 큰 (2의 배수 -1)로 설정

int temp = 1;
void sTreeInit(int n) //n요소 갯수
{
	while (temp < n)
	{
		temp *= 2;
	}
	temp--;
	int j = 0;
	for (int i = temp; i <= temp * 2; i++)
	{
		stree[i].start = j;
		stree[i].end = j;
		j++;
	}
	for (int i = temp - 1; i >= 0; i--)
	{
		stree[i].start = stree[i * 2 + 1].start;
		stree[i].end = stree[i * 2 + 2].end;
	}
}

void sTreeUpdate(int idx, long long value)
{
	int temp2 = temp + idx;
	stree[temp2].value = value;
	while (temp2 > 0)
	{
		temp2 = (temp2 - 1) / 2;
		stree[temp2].value = stree[temp2 * 2 + 1].value + stree[temp2 * 2 + 2].value;
	}
}

long long sTreeGet(int left, int right, int idx) //처음 부를 땐idx=0으로 주면 됨
{
	int s = stree[idx].start, e = stree[idx].end;
	if (left <= s && right >= e)
	{
		return stree[idx].value;
	}
	else if (right < s || left > e)
	{
		return 0;
	}
	else
	{
		return sTreeGet(left, right, idx * 2 + 1) + sTreeGet(left, right, idx * 2 + 2);
	}
}
int main()
{
	int n, m, k;
	long long c;
	int a, b;
	long long dd;
	scanf("%d %d %d", &n, &m, &k);
	sTreeInit(n);
	for (int i = 0; i < n; i++)
	{
		scanf("%lld", &dd);
		sTreeUpdate(i, dd);
	}
	for (int i = 0; i < m + k; i++)
	{
		scanf("%d %d %lld", &a, &b, &c);
		b--;
		if (a == 1)
		{
			sTreeUpdate(b, c);
		}
		else if (a == 2)
		{
			printf("%lld", sTreeGet(b, c - 1, 0));
		}
	}
}

plan222 3년 전 0

출력할때 엔터 하니까 맞네요... 오랜만에 해서 까먹었던것 같습니다

dohoon 3년 전 0

감사합니다..!!!!!

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

문제

문제

출처

ICPC

틀린 곳을 찾아주세요(세그먼트 트리)

plan222 3년 전 0

plan222 3년 전 0

dohoon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말