백준 2268번 수들의 합 7 문제풀이(C++)

백준 2268번 수들의 합 7

아이디어

수들의 합 + 업데이트 => 세그먼트 트리 || 펜윅트리

펜윅트리 : 가볍고 빠르고 수들의 합 + 구현하기 쉬움

문제풀이

sum 의 범위 i, j중 누가 더 큰지 명시가 되어있지 않음을 유의하자...

#include<bits/stdc++.h>
using namespace std;
#define MAX 1'000'000 + 10
typedef long long ll;
ll A[MAX];
ll _sum[MAX];
int n, m;
void Modify(int idx, int k) {
	while (idx <= n + 1) {
		_sum[idx] += k;
		idx += (idx & -idx);
	}
}
ll Sum(int idx) {
	ll sum = 0;
	while (idx) {
		sum += _sum[idx];
		idx -= (idx & -idx);
	}
	return sum;
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	while (m--) {
		int what; cin >> what;
		if (what == 0) {
			int i, j; cin >> i >> j;
			if (i > j)swap(i, j);
			cout << Sum(j) - Sum(i - 1) << '\n';
		}
		else if (what == 1) {
			int i, k; cin >> i >> k;
			Modify(i, k - A[i]);
			A[i] = k;
		}
	}
	return 0;
}