(백준 1275번 커피숍2 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) SegmentTree 5

백준 1275번

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

 

전형적인 segment tree 문제!

#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;
		b -= v[a];
		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 = st.start; i < st.start+ N; i++) {
		cin >> st.v[i];
	}
	st.construct();

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