백준 2042번 - 구간 합 구하기

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

2042번: 구간 합 구하기

일반적인 Prefix Sum으로 구하면 query로 인해 시간 초과가 발생한다.

 

따라서 Binary Index Tree(펜윅 트리)를 사용하여 구해야 하는 문제이다.

 

아래는 BIT에 대한 설명이다.

https://kimtaehyun98.tistory.com/112

Binary Index Tree(BIT, Fenwick Tree)

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, m, k, a, b, c;
vector<ll>A(1000007);
vector<ll>Tree(1000007);

ll sum(ll i) {
	ll ans = 0;
	while (i > 0) {
		ans += Tree[i];
		i -= (i & -i);
	}
	return ans;
}

void update(ll i, ll num) {
	while (i <= n) {
		Tree[i] += num;
		i += (i & -i);
	}
}

int main() {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
		// Tree 생성
		update(i, A[i]);
	}
	for (int i = 0; i < m + k; i++) {
		cin >> a >> b >> c;
		if (a == 1) { // 교체
			ll diff = c - A[b]; // 둘의 차이 구하기
			A[b] = c; // A 배열 교체
			update(b, diff);
		}
		else { // 구간 합 구하기
			// b ~ c 구간 합은 Prefix Sum[c] - Prefix Sum[b-1]와 같다.
			cout << sum(c) - sum(b - 1) << "\n";
		}
	}
}

long long 으로 도배해놨는데 어떤 부분은 int로 쓰고 어떤 부분은 long long으로 쓰는 게 귀찮아서 다 ll로 바꿨다..

 

풀이는 기본적인 BIT 문제이기 때문에 생략한다.