개요

백준 1275(커피숍 2)

• 입력
  첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합을 구하여라, a번째 수를 b로 바꾸어라 라는 뜻의 데이터가 주어진다.

  입력되는 모든 수는 -231보다 크거나 같고, 231-1보다 작거나 같은 정수이다.

• 출력
  한 턴마다 구한 합을 한 줄마다 한 개씩 출력한다.

접근 방식

1. 세그먼트 트리를 이용하여 구간의 합을 저장하는 방식을 택했다.
2. 조심해야할 부분은 문제가아니라 문제 밑에 노트로 적혀있는데,
   
   매우 악랄하다.

전체 코드

#include<iostream>

using namespace std;
//수의 범위가 int 범위 이므로 두 수를 연산하게 되면 int를 넘어갈 수 있음
long long segmentTree[262144];
int N = 0, Q = 0,firstLeafNode=1;


long long Sum(int targetL, int targetR, int nodeNum, int curL, int curR) {
	if (targetR < curL || curR < targetL) return 0;
	if (targetL <= curL && curR <= targetR) return segmentTree[nodeNum];

	int mid = (curL + curR) / 2;
	return Sum(targetL, targetR, 2*nodeNum, curL, mid) + Sum(targetL, targetR, 2*nodeNum+1, mid + 1, curR);
}

//리프노드에서 a번째 인덱스의 수를 b로 바꿔주는 함수
void ChangeElemAndReadjustTree(int a, int b) {
	//리프노드의 a번째 인덱스
	int firstElemIdx = a + firstLeafNode;
	//리프노드의 a번째 인덱스의 변화량, 리프노드의 b번째 인덱스의 변화량
	long long Change = b- segmentTree[firstElemIdx];

	while (firstElemIdx > 0) {
		segmentTree[firstElemIdx] += Change;
		firstElemIdx /= 2;
	}
}

//x부터 y까지의 합 구하기
void SumBetweenTwoIdx(int x, int y) {
	//노트에서 적혀있듯이 x,y순서 바뀌어 있다면 다시 바꿔주자.
	if (x > y) swap(x, y);

	long long Ans = Sum(x, y, 1, 0, firstLeafNode-1);
	cout << Ans<<'\n';
}

void Input() {
	int x=0, y=0, a=0, b=0;
	cin >> N >> Q;
	//리프노드 시작 인덱스 찾기
	while (firstLeafNode < N) {
		firstLeafNode *= 2;
	}
	//리프노드 입력받기
	for (int i = 0; i < N; i++) {
		cin >> segmentTree[firstLeafNode + i];
	}
	//리프노드로부터 부모노드들 갱신하기
	for (int i = firstLeafNode - 1; i > 0; i--) {
		segmentTree[i] = segmentTree[i * 2] + segmentTree[i * 2 + 1];
	}
	for (int i = 0; i < Q; i++) {
		cin >> x >> y >> a >> b;
		SumBetweenTwoIdx(x-1, y-1);
		ChangeElemAndReadjustTree(a - 1, b);
	}


}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
}

문풀후생

문제를 제대로 안 보고,
a번째 수를 b번째 수로 바꾼다고 읽었다.

ChangeElemAndReadjustTreee()함수를 잘못 작성했고,
뭐가 문제인지 상당히 늦게 알았다..
문제 제대로 읽자.

또한 ChangeElemAndReadjustTreee()에서
while문안의 조건을 while(firstElemIdx>0)이 아닌
while(firstElemIdx>1)로 적고말았다.
당연히 루트 노드를 빼먹어서 루트노드만 있는경우에서 계속 틀렸었다.