[백준 ] 2042 구간합 구하기 C++

두번째 풀었던 것임에도 놓쳤던 부분

1.배열 크기를 int 로 했다.-> long long으로 해야한다.

2. 세그먼트 트리 크기를 num 배열이랑 똑같이 해줬다. -> 4배 해야한다.

3.(start+end)/2 로 해야하는데 start+end/2로 했다. ->코드 꼼꼼히 작성하기

4. 함수를 호출할때 num배열은 0에서 N-1까지이기 때문에 start=0,end=N-1로 해줘야하는데

1과 N으로 했다.  다음에는 num배열을 1부터 입력을 받아야겠다. +(b인덱스의 값을 c로 바꾸는 부분도 틀렸다.)

5. 배열의 값을 갱신 시켜줄때 원래 값과 차이를 이용하면 되는데 까먹었다.

다시 한번 풀어봐야겠다.

 

#include<iostream>
#define MAX_TREE (1<<21)



using namespace std;
int N, M, K;
long long a, b, c,dif;

long long num[1000001];
long long sum[MAX_TREE];
//구간 합 트리 만들기
void init(int node, int start, int end) {
	if (start == end) {//더 나눌수 없다.
		
		sum[node] = num[start];
		return;
	}
	else {
		//나누어서 자식 노드들에 저장
		init(node * 2, start, (start + end) / 2);
		init(node * 2 + 1, (start + end) / 2 + 1, end);
		sum[node] = sum[node * 2] + sum[node * 2 + 1];
		return;
	}
}

//값 바꾸기 함수
void change(long long start, long long end, long long node, long long index ,long long dif)//범위: start~end node:범위가 담겨있는 노드번호
{															//index:배열에서 바꾸고 싶은 값이 있는 위치, dif:변경할 값
	if (index > end || index < start)
		return;
	
	sum[node] += dif;
	//자식들도 바꿔준다
	if (start == end)return;
	change(start, (start + end) / 2, node * 2, index, dif);
	change((start+end)/2+1,  end, node * 2+1, index, dif);

}

long long sumN(long long start, long long end, long long left, long long right, long long node)
{
	if (start > right || end < left)
		return 0;
	else if (start >= left && end <= right)
		return sum[node];
	else
	{
		return sumN(start, (start + end) / 2, left, right, node * 2)+ sumN((start + end )/ 2+1,end, left, right, node * 2+1);
	}
}

int main()
{

	cin >> N >> M >> K;

	for (int i = 0; i < N; i++)
		cin >> num[i];

	//구간 합 트리 만들기
	init(1, 0, N-1);
	//cout << sum[1] << "  " << sum[2] << "  " << sum[3] << endl;
	for (int i = 0; i < M + K; i++)
	{
		cin >> a >> b >> c;
		if (a == 1)//b 번째 수를 c로 바꾸기
		{
			
			//차이를 변경해주면 된다.
			
			dif = c - num[b - 1];
			num[b - 1] = c;
			
			change(0, N-1, 1, b-1, dif);
			

			

		}
		else if (a == 2)//b번째부터 c번째까지 합 구하기
		{
			cout<<sumN(0, N-1, b-1, c-1, 1)<<endl;
		}
	}
}