글 읽기 - 2042번 구간합 구하기 BIT로 짰는데

wwiiiii 6년 전 0

왜 틀렸는지를 모르겠습니다 ㅠㅠ

Seq배열은 필요는 없지만 메모리도 넉넉한 김에 계산량 줄여보려고 넣은건데... 뭐가 문제일까요ㅠ 제가 BIT 구현을 잘못한걸까요...

#include <cstdio>
#define GET_LAST_ONE(N) ((N)&(-(N)))

int tree[1000010];
int seq[1000010];//read(i)-read(i-1) = seq[i] 
int n, m, k;

void update(int k, int val)
{
   int index = k;
    while(index<=n)
    {
        tree[index] += val;
        index += GET_LAST_ONE(index);
    } 
}

long long int read(int k)
{
    int index = k;
    long long int sum=0;
    while(index>0)
		{
				sum += tree[index];
				index -= GET_LAST_ONE(index);			
		}    
    return sum;
}

int main()
{
   int a,b,c;
	 scanf("%d %d %d",&n,&m,&k);
	 for(int i=1;i<=n;i++)
	 {
			scanf("%d",&seq[i]);					
			update(i,seq[i])	;				
	 }
	 for(int i=1;i<=m+k;i++)
	 {
			scanf("%d %d %d",&a, &b, &c);
			if(a==1){
					update(b,c-seq[b]);
					seq[b] = c;							
			}
			else{
					printf("%lld\n",read(c)-read(b-1));							
			}
	 }    
}

august14 6년 전 2

tree에 int범위를 넘는 값이 저장될 수도 있는 것 같아요

wwiiiii 6년 전 0

long long으로 고치니까 되네요 ㅠㅠ 감사합니다!

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

문제

문제

출처

ICPC

2042번 구간합 구하기 BIT로 짰는데

wwiiiii 6년 전 0

august14 6년 전 2

wwiiiii 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말