글 읽기 - 구간트리 왜 틀리는 걸까요.

sksdong1 7년 전 0

기본적인 쿼리, 업데이트 아닌가요??

왜 틀리는지 못찾겠네요.. 이상 없어보이는데

import java.util.Scanner;

class Main{
	
	int n,m;
	long tree[] = new long[2100000];
	
	Scanner sc = new Scanner(System.in);
	void solve(){

		n = sc.nextInt();
		m = sc.nextInt();
		
		for(int i=0;i<m;i++){
			int a = sc.nextInt();
			int b = sc.nextInt();
			int k = sc.nextInt();
			if(a==0){
				System.out.println(sum(b, k));
			}
			else if(a==1){
				update(b,k);
			}
		}
	}
	long sum(int left,int right){
		return sum(left,right,1,0,n-1);
	}
	long sum(int left,int right,int node,int start,int end){
		if(end<left || right<start) return 0;
		if(left<=start && end<=right) return tree[node];
		int mid = (start+end)/2;
		return sum(left,right,node*2,start,mid)+sum(left,right,node*2+1,mid+1,end);
	}
	void  update(int idx,int val){
		update(idx,val,0,n-1,1);
	}
	long update(int idx,int val,int start,int end,int node){
		if(start>idx || idx>end) return tree[node];
		if(start==end) return tree[node]=val;
		int mid = (start+end)/2;
		return tree[node] = update(idx,val,start,mid,node*2)+update(idx,val,mid+1,end,node*2+1);
	}
	public static void main(String[] args) {
		new Main().solve();
	}
}

hun222y 7년 전 3

i>j일 경우에는 A[j]+A[j+1]+...+A[i] 이라는 조건이 있어서 만약 1부터 5 의 합을 구하는경우는 맞을거 같은데5 부터 1까지으 ㅣ합을 구하는경우에는 틀릴꺼같네요

kiyaaa 11달 전 0

hun222y님 글 못봤으면 계속 헤맸을 듯 감사합니다.

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

문제

문제

출처

ICPC

구간트리 왜 틀리는 걸까요.

sksdong1 7년 전 0

hun222y 7년 전 3

kiyaaa 11달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말