백준12837 가계부 (Hard)

작성일 | In

문제 링크

  • http://icpc.me/12837

사용 알고리즘

  • Fenwick Tree
  • Segment Tree

시간복잡도

  • O(Q log N)

풀이

전형적인 펜윅 트리 문제입니다.

query(x)는 x까지의 누적합을 구해주므로, [L, R]구간합은 query(R) - query(L-1)로 구해줄 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll tree[1010101];

void add(int x, int v){
	while(x <= 1000000){
		tree[x] += v;
		x += x&-x;
	}
}

ll query(int x){
	ll ret = 0;
	while(x){
		ret += tree[x];
		x -= x&-x;
	}
	return ret;
}

ll query(int l, int r){
	return query(r) - query(l-1);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	while(q--){
		int op, a, b; cin >> op >> a >> b;
		if(op == 1){
			add(a, b);
		}else{
			cout << query(a, b) << "\n";
		}
	}
}