문제 https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 설명 각각의 사탕은 그 맛의 좋고 나쁨이 1부터 1,000,000까지의 정수로 구분된다. 1이 가장 맛있는 사탕을 의미하며, 1,000,000은 가장 맛없는 사탕을 의미한다. A가 1인 경우에는 순위가 B인 사탕을 꺼내는 것이고 2인 경우는 맛이 B인 사탕을 C만큼 넣거나 빼는 것이다. 이를 구현하기 위해 인덱스 트리를 사용한다. if (A == 1) { long ..
문제 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 설명 1. 중간에 수의 변경이 빈번히 일어난다. 2. 그 중간에 어떤 부분의 합을 구하려 한다. N개의 수가 있고 위의 두 조건을 M번 실행한다고 가정한다. 매번 연산을 새로 하는 일반적인 방법으로는 1번 조건의 수행시간은 O(1) 이고 2번 조건의 수행시간은 \(O(N)\) 이다. 최종적으로 \(O(NM)\) 의 시간복잡도를 가진다..
인덱스 트리 (Indexed Tree) 포화 이진 트리 형태의 자료구조 순서를 갖는 정보들이 주어졌을 때, 구간의 대표 값이나 연산 결과를 빠르게 얻을 수 있는 자료구조 구간 합, 구간 내 최댓값, 구간 내 카운트 등을 구할 때 많이 쓰인다. 세그먼트 트리는 인덱스 트리가 포함하고 있는 한 종류이다. 리프 노드 : 배열에 적혀 있는 수 내부 노드 : 왼쪽 자식과 오른쪽 자식의 합 리프 노드의 개수가 S개인 포화 이진 트리는 높이가 logS 이고 총 노드 개수는 (2 x S - 1) 개이다. 인덱스 트리 구현 방법 Top-Down 방식 : DFS 기반 트리 탐색 (재귀 호출) 인덱스 트리 개념을 그대로 코드로 수행 왼쪽 자식 = 2 x node, 오른쪽 자식 = 2 x node + 1 이용 가지치기가 가능..
