세그먼트 트리(기초)

segment_tree_basic.cpp

//2042-구간합구하기
#include <iostream>
#include <algorithm>
using namespace std;

int n, m, k;
long long seg[5000000];

long long update(int pos, int val, int node, int x, int y) {
	/*재귀함수의 기저조건*/
	if (pos < x || y < pos) return seg[node]; // 합해주기 위하여 기다리는 지점
	if (x == y) return seg[node] = val; // 구간이 딱 한 곳

	int mid = (x + y) / 2;
	long long leftchildval = update(pos, val, node * 2, x, mid);
	long long rightchildval = update(pos, val, node * 2 + 1, mid + 1, y);

	return seg[node] = leftchildval + rightchildval;
}

long long query(int low, int high, int node, int x, int y) {
	if (y<low || high < x) return 0;
	if (low <= x && y <= high) return seg[node];

	int mid = (x + y) / 2;
	long long leftchildval = query(low, high, node * 2, x, mid);
	long long rightchildval = query(low, high, node * 2 + 1, mid + 1, y);

	return leftchildval + rightchildval; // seg[node] = left + right 와의 차이..??
}

int main()
{
	scanf("%d %d %d", &n, &m, &k);
	int val;

	for (int i = 0; i < n; i++) {
		scanf("%d", &val);
		update(i, val, 1, 0, n - 1);
	}

	int a, b, c;

	for (int i = 0; i < m + k; i++) {
		scanf("%d %d %d", &a, &b, &c);
		if (a == 1) {
			update(b - 1, c, 1, 0, n - 1);
		}
		else if (a == 2) {
			printf("%lld\n", query(b - 1, c - 1, 1, 0, n - 1));
		}
	}

	return 0;
}

/*
3	1,0
4	-1 
5	0,1
6	2,0
7	-1
8	1,1
9	3,0
10	2,0
11	2,1
12	4,0
13	1,2
14	-1
15	0,3
16	2,2
17	-1
18	1,3
19	3,2
20	0,4

3x+5y = n
*/