[백준/C++] 2042번: 구간 합 구하기

방법

구현 코드

#include<bits/stdc++.h>
#define MAX 1000001 // n의 개수 <= 1,000,000
using namespace std;

int n, m, k, B, t;
long long IDT[MAX * 4];	// n개의 data인 경우 넉넉하게 *4로 설정

void initIDT() {	// 부모 = 자식들의 합으로 트리 구성
	for (int i = B - 1; i > 0; i--) {	// 부모 트리 만들기
		IDT[i] = IDT[i * 2] + IDT[(i * 2) + 1];
	}
}

// p->v 바꾸기
void update(int p, long long v) {
	p += (B - 1);	// p의 index 찾기
	IDT[p] = v;	// 값 바꾸기
	while (p /= 2) {	// root까지 반복
			IDT[p] = IDT[p * 2] + IDT[(p * 2) + 1];	// 부모 = 자식들의 합
	}
}

// l~r까지의 합
long long lgSum(int l, int r) {
	l += (B - 1);	// l과 r의 index 찾기
	r += (B - 1);
	long long sum = 0;
	while (l <= r) {	// l과 r이 cross될 때까지
		if ((l % 2) == 1)	// l이 트리의 right일 때
			sum += IDT[l];
		if ((r % 2) == 0)	// r이 트리의 left일 때
			sum += IDT[r];

		l = (l + 1) / 2;	// 오른쪽 부모 트리로 이동
		r = (r - 1) / 2;	// 왼쪽 부모 트리로 이동
	}
	return sum;	// 구간 합
}

int main() {
	scanf("%d %d %d", &n, &m, &k);
	for (B = 1; B < n; B *= 2);	// 첫번째 index 구하기
	for (int i = B; i < n + B; i++) {
		scanf("%lld", &IDT[i]);
	}
	initIDT();	// indexed tree (합으로 구성)

	t = m + k;
	int a, b;
	long long c;
	// a = 1 (b->c로 바꾸기) / a = 2 (b~c까지의 합)	
	while (t--) {
		scanf("%d %d %lld", &a, &b, &c);
		if (a == 1)
			update(b, c);
		else
			printf("%lld\n", lgSum(b, c));
	}
	return 0;
}