푸으름

✏️ 문제 링크 https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 이 문제 역시 느리게 갱신되는 세그먼트 트리로 구현하는 문제입니다. 여기서 조금 더 생각해 봐야 할 것은 x번째 원소를 출력하는 건데, x번째 인덱스를 구하는 과정은 이분 탐색 과정을 통해서 값을 찾아낼 수 있습니다. 아래 문제는 느리게 갱신되는 세그먼트 트리의 기본 틀을 구현한 문제입니다. https://pooreumjung.t..

머지 소트 트리(Merge Sort Tree)는 트리의 일종으로 merge sort과정을 그대로 트리 모양으로 접합시킨 트리트리의 높이는 log N 정도이고, 하나의 층에 총 N개의 원소가 있으므로 공간복잡도 역시 O(N log N)수준구현이 문제인데, 이것은 merge 함수를 이용하여 생각보다 간단하게 구현이 가능  백준 13537번 수열과 쿼리 1https://www.acmicpc.net/problem/13537 13537번: 수열과 쿼리 1길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다.www.acmicpc.net     각 배열들..