백준 1275번 : 커피숍2 (c++)

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

1275번: 커피숍2

문제

모두 알다시피 동호는 커피숍의 마담이다. (마담이 무엇인지는 본인에게 물어보도록 하자.)

어느 날 커피숍의 손님 A씨가 동호에게 게임을 하자고 했다.

그 게임은 다음과 같은 규칙을 갖는다.

N개의 정수가 있으면, 동호는 다음과 같이 말한다. “3~7번째 수의 합은 무엇이죠?” 그러면 상대방은 “그 답은 000입니다. 그리고 8번째 수를 2로 고치도록 하죠” 그러면 동호는 “네 알겠습니다.”라고 한 뒤에 다시 상대방이 동호가 했던 것처럼 “8~9번째 수의 합은 무엇이죠?”라고 묻게된다. 이 것을 번갈아 가면서 반복하는 게임이다.

당신은 이 게임의 심판 역을 맡았다. 요컨대, 질문에 대한 답들을 미리 알아야 한다는 것이다.

당신의 머리가 출중하다면 10만개 가량 되는 정수와 10만턴 정도 되는 게임을 기억할 수 있을 것이다. 몇판 이 게임을 즐기던 동호는 많은 사람들이 이 게임을 하기를 바라게 되었고, 당신에게 심판 프로그램을 구현해달라고 요청했다.

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

입력되는 모든 수는 32비트 부호있는 정수이다.

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

예제 입력 1 
5 2
1 2 3 4 5
2 3 3 1
3 5 4 1
예제 출력 1 
5
10

#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;
int N, M, K;

vector <ll> num1;

struct IndexedTree {
	vector <ll> tree;
	vector <ll> nums;
	int leafSize = 0, depth = 0;

	IndexedTree(vector <ll> nums1) {
		nums = nums1;
		while (pow(2, depth) < nums1.size() - 1) {
			depth++;
		}
		leafSize = pow(2, depth);
		while (nums.size() <= leafSize) {
			nums.push_back(0);
		}
		tree.resize(pow(2, depth + 1));
	}
	//내부노드에 값을 채워준다.
	ll makeTree(ll node, ll left, ll right) {
		//리프에 도달 하면 데이터를 채워줌
		if (left == right) {
			if (left <= nums.size()) {
				return tree[node] = nums[left];
			}
			else {
				return tree[node] = 0;
			}
		}
		//내부 노드일 경우
		ll mid = (left + right) / 2;
		tree[node] = makeTree(node * 2, left, mid);
		tree[node] += makeTree(node * 2 + 1, mid + 1, right);
		return tree[node];
	}
	//원하는 구간의 합 or 문제에 답을 구한다.

	ll query(ll node, ll left, ll right, ll qLeft, ll qRight) {
		if (qRight < left || right < qLeft) {//관련 없는 경우
			return 0;
		}
		else if (qLeft <= left && right <= qRight) {//완전 속하는 경우
			return tree[node];
		}
		else {//애매하게 걸쳐 있는 경우
			ll mid = (left + right) / 2;
			return query(node * 2, left, mid, qLeft, qRight) +
				query(node * 2 + 1, mid + 1, right, qLeft, qRight);
		}
	}
	//특정값을 갱신한다.
	void update(ll node, ll left, ll right, ll index, ll diff) {
		if (index < left || right < index) {
			return;
		}
		else {
			tree[node] += diff;
			if (left != right) {
				ll mid = (left + right) / 2;
				update(node * 2, left, mid, index, diff);
				update(node * 2 + 1, mid + 1, right, index, diff);
			}
		}
	}
};


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	freopen("input.txt", "r", stdin);
	cin >> N >> M;
	num1.push_back(0);
	ll a, b, c, d;
	for (int i = 0; i < N; i++)
	{
		cin >> a;
		num1.push_back(a);
	}

	IndexedTree h(num1);
	h.makeTree(1, 1, h.leafSize);

	for (int i = 0; i < M; i++)
	{
		cin >> a >> b >> c >> d;
		ll targetIndex = c;
		ll targetValue = d;
		ll diff = targetValue - h.nums[targetIndex];
		if (a < b) {
			cout << h.query(1, 1, h.leafSize, a, b) << "\n";
		}
		else {
			cout << h.query(1, 1, h.leafSize, b, a) << "\n";
		}
		h.update(1, 1, h.leafSize, c, diff);
		h.nums[targetIndex] = targetValue;
	}

	return 0;
}