반응형
https://www.acmicpc.net/problem/2268
2268번: 수들의 합 7
첫째 줄에는 N(1 ≤ N ≤ 1,000,000), M(1 ≤ M ≤ 1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/51
[ 자료구조 ] 세그먼트 트리 (Segment Tree)
1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1
rudalsd.tistory.com
1. 총합이 int형 범위를 벗어나므로 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 | #include<iostream> #define ll long long using namespace std; int N, M; ll segTree[2100000]; int arr[1000001]; ll sum(int node, int start, int end, int sidx, int eidx) { if (end < sidx || start > eidx) return 0; if (sidx <= start && end <= eidx) return segTree[node]; int mid = (start + end) / 2; ll left = sum(node * 2, start, mid, sidx, eidx); ll right = sum(node * 2 + 1, mid + 1, end, sidx, eidx); return left + right; } void modify(int node, int start, int end, int idx, int diff) { if (idx < start || idx > end) return; segTree[node] += diff; if (start != end) { int mid = (start + end) / 2; modify(node * 2, start, mid, idx, diff); modify(node * 2 + 1, mid + 1, end, idx, diff); } } int main() { scanf("%d %d", &N, &M); for (int i = 0; i < M; i++) { int a,b,c; scanf("%d %d %d", &a, &b, &c); if (a == 0) { if (b < c) { printf("%lld\n", sum(1, 1, N, b, c)); } else { printf("%lld\n", sum(1, 1, N, c, b)); } } else { int diff = c - arr[b]; arr[b] = c; modify(1,1,N,b,diff); } } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 17244번 - 아맞다우산 (C++) (0) | 2022.12.31 |
|---|---|
| [ 백준 ] 17497번 - 계산 (C++) (0) | 2022.12.30 |
| [ 백준 ] 1194번 - 달이 차오른다, 가자. (C++) (0) | 2022.12.28 |
| [ 백준 ] 2589번 - 보물섬 (C++) (0) | 2022.12.27 |
| [ 백준 ] 23793번 - 두 단계 최단 경로 1 (C++) (0) | 2022.12.26 |