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

문제

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

2042번: 구간 합 구하기

---

문제 요약

N개의 수가 배열 A에 저장되어 있다.

 

중간에 A[i]의 변경이 빈번히 일어날 때, 어떤 부분의 합을 구하려고 한다.

---

코드

#include <iostream>
#include <algorithm>

#define ll long long
#define MAX_N 1000000

using namespace std;

ll n, m, k;

ll A[MAX_N + 1];
ll tree[MAX_N + 1];

// 1 ~ i번 인덱스 까지의 누적합 반환 (prefix[i])
ll sum(ll i) {
	ll ans = 0;
	while (i > 0) {
		ans += tree[i];
		i -= (i & -i);
	}
	return ans;
}

// tree[i]를 tree[i] + num으로 수정
void update(ll i, ll num) {
	// int ori = i;
	while (i <= n) {
		tree[i] += num;
		i += (i & -i);
	}
}

int main() {
	// 수의 개수, 수의 변경이 일어나는 횟수, 구간 합을 구하는 횟수
	cin >> n >> m >> k;

	for (ll i = 1; i <= n; i++) {
		cin >> A[i];

		// 트리 설정
		update(i, A[i]);
	}

	for (ll i = 0; i < m + k; i++) {
		ll a, b, c;
		cin >> a >> b >> c;

		if (a == 1) {
			update(b, c - A[b]);
			A[b] = c;
		}
		else {
			cout << sum(c) - sum(b - 1) << "\n";
		}
	}
}

---

코드 설명

https://daily-program-ing.tistory.com/226

BIT (Binary Indexed Tree)

 

기본적인 BIT의 개념은 위 글을 참고하기 바랍니다.

 

1. tree의 모든 초기값을 0으로 설정하고, A[i]를 입력 받을 때마다 update 함수를 호출하여 트리를 값을 초기화한다.

 

2. a, b, c를 쿼리 수 만큼 입력 받고 처리한다.

 

2 - 1. a가 1이라면, A[b]와 그 변화에 따른 tree를 갱신해준다.

+ A[b]를 먼저 갱신하면, update를 호출 시 바뀐 A[b]의 값을 파라미터로 넘겨줌에 유의한다.

 

2 - 2. a가 2라면, A[b]부터 A[c] 까지의 합을 구해야 함으로 Prefix[c] - Prefix[b - 1]를 출력한다.

+ Prefix[c] - Prefix[b]를 하면 A[b + 1]부터 A[c]까지 합이므로 유의한다.