글 읽기 - 세그먼트트리 질문입니다

jh20s 7년 전 0

세그먼트트리로 처음푸는 문제라 블로그 참고해서 풀었습니다

구간을 [0,n-1]로 잡고 세그먼트트리로 풀었는데 어느 부분이 문제인지 찾을수가 없네요 ㅠㅠ...

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<functional>
using namespace std;

int h = 1;
long long arr[4000000];

void update(int i, int n) {
	i += h;
	arr[i] = n;
	while (i > 1) {
		i /= 2;
		arr[i] = arr[i * 2] + arr[i * 2 + 1];
	}
}	

long long sum(int L, int R, int nodenum, int nodeL, int nodeR) {
	if (L <= nodeL&&nodeR <= R) return arr[nodenum];
	if (nodeR < L || R < nodeL) return 0;
	int mid = (nodeL + nodeR) / 2;
	return sum(L, R, nodenum * 2, nodeL, mid) + sum(L, R, nodenum * 2 + 1, mid + 1, nodeR);
}

int main(void) {
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	m += k;
	while (n > h) h *= 2;
	for (int i = 0; i < n; i++) 
		scanf("%lld", &arr[i + h]);
	for (int i = 0; i < n; i++) update(i, arr[i + h]);
	
	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		if (a == 1)
			update(b-1, c);
		else if(a==2)
			printf("%lld\n", sum(b-1, c-1, 1, 0, n - 1));
	}
}

ae04071 7년 전 0

쿼리 for문에 i < m이 아니라 i < m + k 가 아닐까요...??

jh20s 7년 전 0

m += k;로 해놔서 그건 아닌거같아요 ㅠㅠ..

ae04071 7년 전 1

아아 죄송합니다;;

대신에 다른 에러를 찾아왔어요!

a = 1 인풋받을때 아마 c가 int범위 내이 있다는 가정이 없을꺼에여;;; 그리고 이것 말고

sum 호출할 때 n-1 대신에 h - 1을 대입하면 됩니다.

Update에서는 BIT 개념을 이용했고, sum에서 세그트리를 이용해서 문제가 생긴거같아여

리프노드의 개수가 총 h개가 있는대 n개의 구간에 대해서만 처리를 해줘서 그럽니다;;

설명을 잘 못해서;; 다른 분들 글 읽어보시면 좋을 것 같아여;;

jh20s 7년 전 0

아 그렇네요 ㅠㅠㅠ 이부분 때문에 어제 엄청 고생많이 했는데

처음 쿼리 범위가 [0,h-1] 범위인데 제가 [0,n-1]로 잡아서 문제가 있었네요

감사합니다 ㅠㅠㅠㅠ

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

문제

문제

출처

ICPC

세그먼트트리 질문입니다

jh20s 7년 전 0

ae04071 7년 전 0

jh20s 7년 전 0

ae04071 7년 전 1

jh20s 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말