코딩못하는사람

www.acmicpc.net/problem/12899 12899번: 데이터 구조 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니 www.acmicpc.net 1.접근 N이 2,000,000이므로 NlogN을 생각하게된다. 세그먼트 트리를 이용할텐데 X의 크기도 2000000까지인 것을 보아 리프노드를 200만개로 만들고 1번 유형 쿼리로 숫자와 인덱스가 같은 트리를 만들어야겠다. 2.풀이 우선 트리를 만드는대 어느 숫자가 들어올지 모르기 때문에 리프노드 200만개 모두 만들어야 한다. 그 후 인덱스와 들어오는 숫자가 같은 트리이므로 ..

16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net 1.접근 N은 십만 M도 십만이다. N^2으로 해결 불가능하고 NlogN으로 해결한다고 생각했다. 구간 합을 구하는 문제가 아닌 구간에 k를 더하는 문제이다. 생각을 조금 바꿔보자. 세그먼트 트리와 관련되서 생각해보니 1번 쿼리가 들어왔을 때 각 리프노드에 k를 더하지 않고 구간에 해당되는 노드에 k를 넣어놓고 출력할때 꺼내가면 된다고 생각했다. 2.풀이 우선 하던대로 완전 이진 트리를 리프노드만 전처리한다. 리프위에 노드들은 구간합같은 문제가..

세그먼트 트리란? 세그먼트 트리(Segment Tree) 또는 인덱스 트리(Index Tree)는 다음 두 연산을 어떻게 더 효율적으로 할까에 대한 고민에서 출발한다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 i번째 수를 v로 바꾸기. A[i] = v 두번째 연산은 O(1)에 해결할 수 있겠지만 첫 번째 연산은 l-r의 길이만큼의 시간 O(NM)이 쿼리가 요청될 때 마다 소요될 것이다. (쿼리 m번 구간크기 n) 따라서 우리는 M과 N이 클때를 위한 자료구조인 세그먼트 트리를 알아야한다. 가장 기본적인 2,3,7,4,5,9,6,1의 구간합을 구하는 세그먼트 트리를 보자. 트리는 완전 이진 트리로 구성된다. 또한 트리의 ..