[백준][C++] 12837: 가계부 (Hard)

문제 링크: https://www.acmicpc.net/problem/12837

 

세그먼트 트리 문제입니다. 구간합 세그먼트 트리로 풀면 되는데...

업데이트 쿼리의 경우 배열 값을 업데이트하는게 아니고, 배열 값에 추가를 해줘야 합니다. 문제를 잘 안읽어서 헤맸네요;;;

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;




// sum
vector<ll> tree;

// node -> 1
// [node_l, node_r] -> [0, n-1]
//int init(vector<int>& arr, int node_l, int node_r, int node) {
//	if (node_l == node_r) return tree[node] = arr[node_l];
//
//	int mid = (node_l + node_r) / 2;
//	return tree[node] = init(arr, node_l, mid, node * 2) + init(arr, mid + 1, node_r, node * 2 + 1);
//}

ll query(const int& l, const int& r, int node_l, int node_r, int node) {
	if (r < node_l || node_r < l) return 0;	// 구간과 겹치지 않는 경우
	if (l <= node_l && node_r <= r) return tree[node];	// node 표현범위가 arr[l, r]에 포함되는 경우

	int mid = (node_l + node_r) / 2;
	return query(l, r, node_l, mid, node * 2) + query(l, r, mid + 1, node_r, node * 2 + 1);
}

ll update(const int& idx, const ll& newValue, int node_l, int node_r, int node) {
	if (idx < node_l || node_r < idx) return tree[node];	// 구간과 겹치지 않는 경우
	if (node_l == node_r) return tree[node] += newValue;		// leaf

	int mid = (node_l + node_r) / 2;
	return tree[node] = update(idx, newValue, node_l, mid, node * 2) + update(idx, newValue, mid + 1, node_r, node * 2 + 1);
}


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n, q;
	cin >> n >> q;
	tree.resize(4 * n);

	while (q--) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) {
			update(b - 1, c, 0, n - 1, 1);
		}
		else {
			cout << query(b - 1, c - 1, 0, n - 1, 1) << '\n';
		}
	}

	return 0;
}