백준 1275 c++ "커피숍2" -PlusUltraCode-

https://www.acmicpc.net/problem/1275

 

[필자 사고]

이 문제는 세그먼트 트리를 이용하면 쉽게 풀 수 있따.

ㄷㅏ만 조심해야 될 부분은 갱신 부분인데 갱신할 부분을 숫자로 대체하고 다시 합을 구하는게 아닌

기존값과 갱신값의 차이를 구한뒤 idx/=2 방식으로 값만 갱신해주면 시간복잡도 내에 문제를 해결할 수 있다.

아래는 코드해설이다.

[코드 해설]

1. Input 함수

• 배열의 크기 N과 명령 수 M을 입력받습니다.
• 입력된 값은 배열 arr에 저장됩니다.

---

2. Init_Segment_Tree 함수

• 세그먼트 트리를 초기화합니다:
  • 트리 크기 계산:
    • treeHeight: 배열 크기 N에 대한 로그 값을 계산하여 트리의 높이를 결정합니다.
    • treeSize: 트리 전체의 노드 개수를 계산합니다.
    • leftStartIdx: 리프 노드가 시작되는 인덱스를 저장합니다.
  • 리프 노드 초기화:
    • 입력 배열 arr의 값을 리프 노드(tree[i + leftStartIdx])에 복사합니다.
  • 내부 노드 초기화:
    • 부모 노드는 두 자식 노드의 합으로 구성됩니다.

---

3. Query 함수

• 구간 [start, end]의 합을 구합니다:
  • start와 end를 리프 노드의 인덱스로 변환합니다.
  • sum 변수에 구간의 값을 저장합니다.
  • 구간 합 계산:
    • start가 홀수인 경우 해당 노드 값을 더하고, 오른쪽으로 이동합니다.
    • end가 짝수인 경우 해당 노드 값을 더하고, 왼쪽으로 이동합니다.
  • start와 end를 부모 노드로 이동하며 반복합니다.
• 최종적으로 구간 합(sum)을 반환합니다.

---

4. Update_Tree 함수

• 배열의 특정 위치 idx의 값을 value로 업데이트합니다:
  • idx를 리프 노드의 인덱스로 변환합니다.
  • 현재 값과 새 값의 차이(diff)를 계산합니다.
  • diff를 반영하여 현재 노드와 모든 부모 노드의 값을 갱신합니다.

---

5. Game_Start 함수

• 세그먼트 트리를 초기화합니다.
• 각 명령에 대해 다음 작업을 수행합니다:
  1. 구간 합 계산:
     • [x1, y1] 구간의 합을 Query 함수로 계산합니다.
     • 결과를 출력합니다.
  2. 값 업데이트:
     • 배열의 a번째 값을 b로 변경합니다.
     • Update_Tree 함수로 트리를 갱신합니다.

---

6. main 함수

• Input 함수로 데이터를 입력받습니다.
• Game_Start 함수로 게임을 실행합니다.
• 입출력 속도를 높이기 위해 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)를 사용합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int N, M;
vector<long> arr;
vector<long> tree;
int treeHeight, treeSize, leftStartIdx;

void Input() {
	cin >> N >> M;
	arr.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

}

void Init_Segment_Tree() {
	treeHeight = (int)ceil(log2(N));
	treeSize = (1 << (treeHeight + 1));
	leftStartIdx = treeSize / 2;

	tree.resize(treeSize);

	for (int i = 0; i < N; i++) {
		tree[i + leftStartIdx] = arr[i];
	}

	for (int i = leftStartIdx - 1; i > 0; i--) {
		tree[i] = tree[i * 2] + tree[i * 2 + 1];
	}
}
long Query(int start, int end) {
	
	start += leftStartIdx;
	end += leftStartIdx;

	long sum = 0;

	while (start <= end) {
		if (start % 2 == 1) {
			sum += tree[start];
			start++;
		}
		if (end % 2 == 0) {
			sum += tree[end];
			end--;
		}

		start /= 2;
		end /= 2;
	}

	return sum;
}
void Update_Tree(int idx, int value) {
	idx += leftStartIdx;
	long nowValue = tree[idx];
	long diff = value - nowValue;

	while (idx != 0) {
		tree[idx] += diff;
		idx /= 2;
	}
}

void Game_Start() {
	Init_Segment_Tree();

	for (int i = 0; i < M; i++) {
		int x1, y1, a, b;
		cin >> x1 >> y1 >> a >> b;

		int  x = min(x1, y1);
		int y = max(x1, y1);

		cout << Query(x - 1, y - 1) << '\n';
		Update_Tree(a - 1, b);
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	Input();
	Game_Start();
}