(백준 12837번 가계부(Hard) C++) 라이님 블로그 대회 알고리즘 따라잡기 12) SegmentTree 4

이제 진짜 익숙해지고 있다!!!! 가자 Segment Tree!

 

백준 12837번

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

#include <iostream>
#include <vector>
using namespace std;

struct segTree {
	int n, start;
	vector<long long > v;
	segTree(int n) : n(n) {
		start = 1;
		while (start < n) start *= 2;
		v.resize(2 * start);
		fill(v.begin(), v.end(), 0);
	}

	void construct() {
		for (int i = start - 1; i > 0; i--) {
			v[i] = v[i * 2] + v[i * 2 + 1];
		}
	}

	void add(int a, long long b) {
		a += start;
		while (a > 0) {
			v[a] += b;
			a /= 2;
		}
	}

	long long sum(int a, int b) { return sum(a, b, 1, 0, start); }
	long long sum(int a, int b, int node, int na, int nb) {
		if (nb <= a || b <= na) return 0;
		if (a <= na && nb <= b) return v[node];
		int mid = (na + nb) / 2;
		return sum(a, b, node * 2, na, mid) + sum(a, b, node * 2 + 1, mid, nb);
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, Q; cin >> N >> Q;
	segTree st(N);

	for (int i = 0; i < Q; i++) {
		int a, b; long long c;
		cin >> a >> b >> c;
		if (a == 1) st.add(b - 1, c);
		if (a == 2) cout << st.sum(b - 1, c) << "\n";
	}
	return 0;
}

 

 

딱히 앞에서 풀었던 풀이와 다른 점은 없다. 다만 숫자를 갈아끼는 문제들과 다르게 원래 있는 노드에 더해줘야 한다는 점 정도만 달라졌다!