[BOJ] 2042. 구간 합 구하기

문제 원본 : https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

#include <iostream>
#include <vector>

using namespace std;

long long n[1000000];
long long arr[4000000];

long long init(int node, int l, int r) {
	if (l == r) {
		return arr[node] = n[l];
	}
	int mid = (l + r) / 2;
	return arr[node] = init(node * 2, l, mid) + init(node * 2 + 1, mid + 1, r);
}

long long query(int l, int r, int node, int nl, int nr) {
	if (r<nl || l>nr) {
		return 0;
	}

	if (l<=nl && nr <= r) {
		return arr[node];
	}

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

long long update(int index, long long newValue, int node, int l, int r) {
	if (index < l || index > r) {
		return arr[node];
	}

	if (l == r) {
		return arr[node] = newValue;
	}

	int mid = (l + r) / 2;
	return arr[node] = update(index, newValue, node * 2, l, mid) + update(index, newValue, node * 2 + 1, mid + 1, r);
}

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

	long long N, M, K;
	long long a, b, c;
	cin >> N >> M >> K;
	for (int i = 0; i < N; ++i) {
		cin >> n[i];
	}

	init(1, 0, N - 1);

	for (int i = 0; i < M + K; ++i) {
		cin >> a >> b >> c;
		if (a == 1) {
			update(b - 1, c, 1, 0, N - 1);
		}
		else {
			cout << query(b - 1, c - 1, 1, 0, N - 1) << "\n";
		}
	}
}

• 세그먼트 트리 기본