문제링크 : https://www.acmicpc.net/problem/2042
문제 접근
- 세그먼트 트리 문제 : https://dev-jango.tistory.com/30
시간복잡도 계산
- 처음 세그먼트 트리 생성 : N * lgN
- M+K번 의 수정 및 출력 : (M+K)*lgN
- O((N+M+K) * lgN) = 1e6 * 20 = 2e7
인트 계산
- 세그먼트 트리 값 : 최대값인 2^63이 1e6개 있을경우 제일 상단값은 2^63 * 1e6 = e18 * e6 = e24 >> long long
- 입력으로 들어오는값 모두 최대 2^63 > long long
코드
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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | #include <iostream> #include <queue> #include <cmath> using namespace std; typedef long long ll; vector<ll> tree; int nums[1000010]; ll make(int node, int st, int en) { // 시작값과 끝값이 같으면 종료 if(st == en) return tree[node] = nums[st]; int mid = (st+en)/2; ll rsl = make(node*2, st, mid); ll rsr = make(node*2+1, mid+1, en); // st ~ mid, mid+1 ~ en 의 합으로 리턴 return tree[node] = rsl + rsr; } void update(int node, int st, int en, int idx, ll diff) { if(idx < st || en < idx) return; tree[node] += diff; if(st != en) { int mid = (st+en)/2; update(node*2, st, mid, idx, diff); update(node*2+1, mid+1, en, idx, diff); } return; } ll sumt(int node, int st, int en, int li, int ri) { if (ri < st || en < li) return 0; if(li <= st && en <= ri) return tree[node]; int mid = (st+en)/2; ll rsl = sumt(node*2, st, mid, li, ri); ll rsr = sumt(node*2+1, mid+1, en, li, ri); return rsl + rsr; } int main() { ios::sync_with_stdio(0); cin.tie(0); int N,M,K; cin >> N >> M >> K; for(int i=0; i<N; i++) cin >> nums[i]; // 세그먼트 크기 초기화 int h = ceil(log2(N)); tree.resize(1<<(h+1)); // 초기 세그먼트 트리 생성 make(1,0,N-1); for(int i=0; i<M+K; i++) { int a,b; cin >> a >> b; ll c; cin >> c; if(a==1) { ll diff = c - nums[b-1]; nums[b-1] = c; // 구간 업데이트 update(1,0,N-1,b-1, diff); } else { // 구간합 구함 cout << sumt(1,0,N-1,b-1,c-1) << '\n'; } } return 0; } | cs |
문제유형
- 세그먼트 트리
비슷한 문제
- 세그먼트 lazy : https://www.acmicpc.net/problem/10999
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 1937 욕심쟁이 판다 풀이(C++/CPP) (0) | 2021.02.14 |
|---|---|
| 백준 10999 구간 합 구하기2 쉬운 풀이(C++/CPP) (0) | 2021.02.14 |
| 백준 11657 타임머신 쉬운 풀이(C++/CPP) (0) | 2021.02.14 |
| 백준 11779 최소비용 구하기 2 쉬운 풀이(C++/CPP) (0) | 2021.02.14 |
| 백준 11780 플로이드2 풀이(C++/CPP) (0) | 2021.02.08 |