백준 12837 - 가게부(Hard) (C++)

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

 

세그먼트  트리를 이용한 문제입니다.

세그먼트 트리를 이용해 푸는 문제입니다.

 

p일에 수입/지출이 계속 주어졌을 때, 원하는 날까지의 합을 구하는 문제입니다. 

N의 범위가 10^6까지이기에 일반적인 방법으로 더한다면 시간 초과가 생깁니다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
#define INF 987654321

using namespace std;

int N, Q;
long long Index[1000001];
vector<long long> Tree;

long long segment_tree(int st, int fin, int node) {
	if (st == fin) return Tree[node] = Index[st];
	int mid = (st + fin) / 2;
	long long left = segment_tree(st, mid, node * 2);
	long long right = segment_tree(mid + 1, fin, node * 2 + 1);
	return Tree[node] = (left + right);
}

long long get_sum(int node, int st, int fin, int left, int right) {
	if (right < st || left > fin) return 0;
	if (left <= st && right >= fin) return Tree[node];
	int mid = (st + fin) / 2;
	long long left_sum = get_sum(node * 2, st, mid, left, right);
	long long right_sum = get_sum(node * 2 + 1, mid + 1, fin, left, right);
	return (left_sum + right_sum);
}

void change_tree(int node, int st, int fin, int loc, long long diff) {
	if (loc < st || loc > fin) return;
	Tree[node] += diff;
	if (st != fin) {
		int mid = (st + fin) / 2;
		change_tree(node * 2, st, mid, loc, diff);
		change_tree(node * 2 + 1, mid + 1, fin, loc, diff);
	}
}

void solve() {
	int height = ceil(log2(N));
	Tree.resize(1 << (height + 1));
	segment_tree(0, N - 1, 1);
	for (int i = 1; i <= Q; i++) {
		long long a, p, x;
		scanf("%lld %lld %lld", &a, &p, &x);
		if (a == 1) { // 값을 추가한다.
			change_tree(1, 0, N - 1, p - 1, x);
			Index[p - 1] += x;
		}
		else { // 변화한 양을 출력한다.
			cout << get_sum(1, 0, N - 1, p - 1, x - 1) << "\n";
		}
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> Q;
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.