세그먼트 트리

[백준 1280] 나무심기 (C++)

1280번: 나무 심기 첫째 줄에 나무의 개수 N (2 ≤ N ≤ 200,000)이 주어진다. 둘째 줄부터 N개의 줄에 1번 나무의 좌표부터 차례대로 주어진다. 각각의 좌표는 200,000보다 작은 자연수 또는 0이다. www.acmicpc.net 세그먼트 트리를 응용하는 문제 tree 배열은 나무를 심을 수 있는 좌표의 구간(0 ~ 200000)을 node번호로 하는 세그먼트 트리이다. 0 ~ 200000 : 1번 노드, 0 ~ 100000 : 2번 노드, 100001 ~ 200000 : 3번노드 ...... 각 구간에 속하는 나무의 개수가 tree[node].first에 저장된다. 각 구간의 나무 위치의 합이 tree[node].second에 저장된다. 이 정보들이 왜 필요한가?? 새로운 나무를 심을..

[백준 1395] 스위치 (C++)

1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 세그먼트 트리 오랜만의 백준 풀이다. 어저께 하루 종일 고민하면서 구현했고 방금 구현을 마무리해서 AC를 받았다. 처음엔 3653 영화 수집 문제를 풀려고 했는데 아무리 생각해도 푸는 방법이 생각이 안 나서 런하고 만난 문제가 이번 문제다. 도망쳐서 만났기 때문에 한번 더 도망칠 수가 없었다.. 전에 풀었던 구간합구하기2 문제랑 느낌이 비슷해서 레이지 세그먼트 트리로 감을 잡았다. [백준 10999] 구간 합 구하기 2 (..

[백준 2517] 달리기 (C++)

2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 세그먼트 트리 최대 50만명의 선수들의 실력이 1부터 10억까지의 범위를 가지고 주어진다. 선수들의 등수는 상대적이므로 실력을 10억까지 되는수로 가지고 있을 필요가 없다. 정렬을 사용해서 선수들의 실력을 1~N까지의 수로 조정해준다. 그리고 주어진 선수들을 한명씩 세그먼트 트리에 넣으면서 자신보다 앞서 있지만 자신보다 실력이 낮은 선수의 수를 구한다. 세그먼트 트리의 구간은 선수들의 실력이 된다. 각 노드의 값은 해당 실력에 속한 선수들의 수가 된다. 트..

[백준 2243] 사탕상자 (C++)

2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. www.acmicpc.net 세그먼트 트리 이 문제는 array값이 주어지지 않는다. 그럼 트리를 어떻게 만드는가? 사탕의 맛이 1부터 1,000,000 까지의 정수로 표현된다고 한다. 그래서 사탕의 맛을 트리의 인덱스(구간)로 설정하면 되고 사탕의 맛의 개수를 트리의 값으로 설정하면 풀 수 있다. [백준 1321] 군인 C++ 1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주..

[백준 10999] 구간 합 구하기 2 (C++)

10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 세그먼트 트리, Lazy propagation 처음에 그냥 세그먼트 트리를 사용했다. 구간을 update할 때마다 리프노드까지 들어가서 update하고, 되돌아오면서 update값을 더해서 tree에 적용해줬다. 제출하면서도 매우 찝찝했다. 값을 수정하는 구간이 1~N까지라면 값을 update하는데 N의 시간이 걸리게 될 것이다.. 구간합을 찾는 쿼리는 log(N)이라서 둘을 더하면 O(NM + K..

[백준 1275] 커피숍2 (C++)

1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 세그먼트 트리 [백준 11505] 구간 곱 구하기 (C++) 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고. hyeo-noo.tistory.com 위 문제와 똑같은 문제이다. a번째수를 b로 바꾸어야 하므로 a번째 수를 포함하고 ..

[백준 1321] 군인 C++

1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개 www.acmicpc.net 세그먼트 트리 10개월 만에 다시 풀어보는 세그먼트 트리문제이다. 우선 a ~ b 구간의 부대의 인원의 합을 하나의 노드로 잡고 세그먼트 트리를 만들었다. 특정 부대의 증원이나 감원을 할 때는 업데이트 쿼리를 만들어서 수행했다. ex) 2번 부대의 인원이 늘어났다면 1-5번, 1-3번, 2번 노드의 인원이 모두 같은 수 만큼 증가해야 한다. 마지막으로 군인을 배치하는 arrangement쿼리를 만들었다. 군인의 번호가 왼쪽 자식 노드의 최대 인원보..