세그먼트 트리

[2042] 구간 합 구하기

문제

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b(1 ≤ b ≤ N)번째 수를 c로 바꾸고 a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 합을 구하여 출력하면 된다.

입력으로 주어지는 모든 수는 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.

출력

첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.

 

#include<iostream>
#include<cmath>
#include<vector>
#define mid (s+e)/2
using namespace std;

long long arr[1000000];
vector<long long> tree;

long long init(int s, int e, int n) {
    
	if (s == e) return tree[n] = arr[s];

	return tree[n] = init(s, mid, n * 2) + init(mid + 1, e, n * 2 + 1);
}

long long sum(int s, int e, int n, int l, int r) {

	if (l > e || r < s) return 0;
	if (l <= s && e <= r) return tree[n];

	return sum(s, mid, n * 2, l, r) + sum(mid + 1, e, n * 2 + 1, l, r);
}

void update(int s, int e, int n, int idx, long long diff) {

	if (idx < s || e < idx) return;

	tree[n] += diff;

	if (s == e) return;

	update(s, mid, n * 2, idx, diff);
	update(mid + 1, e, n * 2 + 1, idx, diff);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int N, M, K;
    cin >> N >> M >> K;
	for (int i = 0; i < N; i++) cin >> arr[i];

	int h = ceil(log2(N));
	tree.resize(1 << (h + 1));
	init(0, N - 1, 1);
    
	for (int i = 0; i < M + K; i++) {
		int a, b; long long c;
		cin >> a >> b >> c;
		if (a == 1) {
			long long diff = c - arr[b - 1];
			arr[b - 1] = c;
			update(0, N - 1, 1, b - 1, diff);
		}
		else
			cout << sum(0, N - 1, 1, b - 1, c - 1) << '\n';
	}
}

[14438] 수열과 쿼리 17

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109)
• 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을 출력한다. (1 ≤ i ≤ j ≤ N)

수열의 인덱스는 1부터 시작한다.

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#define mid (s+e)/2
using namespace std;

int arr[100001];
vector<int> tree;

int init(int s, int e, int n) {

	if (s == e) return tree[n] = arr[s];

	init(s, mid, n * 2);
	init(mid + 1, e, n * 2 + 1);

	return tree[n] = min(tree[n * 2], tree[n * 2 + 1]);
}

void update(int s, int e, int n, int idx, int val) {

	if (idx < s || e < idx) return;

	if (s == e) {
		tree[n] = val;
		return;
	}

	update(s, mid, n * 2, idx, val);
	update(mid + 1, e, n * 2 + 1, idx, val);
	tree[n] = min(tree[n * 2], tree[n * 2 + 1]);
}

int query(int s, int e, int n, int l, int r) {
	if (l > e || r < s) return 2147483647;
	if (l <= s && e <= r) return tree[n];

	return min(query(s, mid, n * 2, l, r), query(mid + 1, e, n * 2 + 1, l, r));
}

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

	int N; cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];

	int h = ceil(log2(N));
	tree.resize(1 << (h + 1));
	init(1, N, 1);

	int M; cin >> M;

	for (int x = 0; x < M; x++) {
		int a; cin >> a;
		if (a == 1) {
			int i, v; cin >> i >> v;
			update(1, N, 1, i, v);
		}
		else {
			int i, j; cin >> i >> j;
			cout << query(1, N, 1, i, j) << '\n';
		}
	}
}