백준1275 커피숍2

작성일 | In

문제 링크

  • http://icpc.me/1275

사용 알고리즘

  • Segment Tree

시간복잡도

  • O(Q log N)

풀이

너무 대놓고 세그먼트 트리를 쓰라고 문제에서 말해주고 있습니다.
update와 query만 이쁘게 구현해주면 됩니다.

전체 코드

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Seg{
	ll tree[401010];
	int bias;

	void init(int n){
		for(bias=1; bias<n; bias<<=1);
	}

	void build(){
		for(int i=bias-1; i>=1; i--){
			tree[i] = tree[i<<1] + tree[i<<1|1];
		}
	}

	void update(int x, ll v){
		x |= bias; tree[x] = v;
		while(x >>= 1){
			tree[x] = tree[x<<1] + tree[x<<1|1];
		}
	}

	ll query(int l, int r){
		l |= bias, r |= bias;
		ll ret = 0;
		while(l < r){
			if(l & 1) ret += tree[l++];
			if(!(r & 1)) ret += tree[r--];
			l >>= 1, r >>= 1;
		}
		if(l == r) ret += tree[l];
		return ret;
	}
} seg;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	seg.init(n);
	for(int i=1; i<=n; i++){
		cin >> seg.tree[i | seg.bias];
	}
	seg.build();

	while(q--){
		int x, y, a; ll b; cin >> x >> y >> a >> b;
		if(x > y) swap(x, y);
		cout << seg.query(x, y) << "\n";
		seg.update(a, b);
	}
	return 0;
}