전체 글 (774) 썸네일형 리스트형 차분 배열 [19551] [1. 문제 설명]https://www.acmicpc.net/problem/19951[2. 코드] 차분 배열 [1. 개요]차분 배열은 배열을 효율적으로 구간 단위로 갱신 할 수 있도록 해주는 자료 구조이다.[a. b] 구간에 대해서 +k 를 하고,[c, e] 구간에 대해서 +m 을 하고,...이와 같은 방식으로, 구간 내 변화가 발생한다고 했을 때,단순한 방법으로는 각 구간을 iterate 하면서 업데이트 하는 방법 이 있지만,결국 필요한 구간 만큼 iterate 해야 하는 상황이 발생하게 된다.즉, 쿼리 개수 (Q) 와 구간의 길이 (L) 에 대해서 시간 복잡도 O(Q * L) 이 발생하게 된다. 그러나 차분 배열을 이용하면 동일한 작업에 대해서 시간 복잡도를 O(Q + L) 로 낮출 수 있다.[2. 차분 배열의 정의]어떤 배열 A 가 있을 때, 차분 배열 D 는 아래와 같이 정의 된다.D[0] = A[0]D.. radix tree [1. 개요] [3. 코드] 이전 1 ··· 10 11 12 13 14 15 16 ··· 258 다음