백준 1275번 커피숍2

문제링크: https://www.acmicpc.net/problem/1275

사용한 알고리즘: 펜윅트리


펜윅트리...를 아신다면 풀 수 있는 문제였습니다....
혹시 펜윅트리에대한 자세한 내용이 궁금한 분들은 아래 링크에 잘 정리되어 잇으니 참고해주세요.
https://www.acmicpc.net/blog/view/21

문제풀이는 다음과 같습니다.
(1) 먼저 N번 주어지는 수들로 펜윅트리를 업데이트(구성) 해줍니다.
(2) 이후 M번 주어지는 x,y,a,b 입력에서, x~y 수의 합을 출력해주고 a번째수를 b로 업데이트 해줍니다.

	#include <bits/stdc++.h>
	using namespace std;
	#define ll long long
	const ll MAX = 111111;
	ll N, Q;
	ll tree[MAX+1], arr[MAX+1];
	ll Li(ll x){
	return x&(-x);
	}
	ll sum(ll i){
	ll ans = 0;
	while(i>0){
	ans += tree[i];
	i -= Li(i);
	}
	return ans;
	}
	void update(ll i, ll diff){
	while(i<=MAX){
	tree[i] += diff;
	i += Li(i);
	}
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> Q;
	for(ll i = 1; i <= N; ++i){
	ll num;
	cin >> num;
	arr[i] = num;
	update(i,num);
	}
	while(Q--){
	ll x, y, a, b;
	cin >> x >> y >> a >> b;
	if(y<x) swap(x,y);
	cout << sum(y)-sum(x-1) << '\n';
	ll dif = b-arr[a];
	update(a,dif);
	arr[a] = b;
	}
	return 0;
	}

view raw BOJ 1275.cpp hosted with ❤ by GitHub