segment tree (6) 썸네일형 리스트형 184. Continuous Sum Segment Tree DP로 해결할 수 있는 문제 중 수열에서 최대 연속합을 구하는 문제가 있다. 이전에 소개한 적이 없으므로 여기서 소개를 하자면 다음과 같다. 아래 문제를 보자. BOJ 1912. 연속합 (Silver II) $n$개의 수가 주어지고 그것을 각각 $a_1, a_2, \ldots, a_n$이라고 했을 때 두 인덱스 $i$와 $j$를 잘 정해서 $a_i + a_{i + 1} + \ldots + a_{j - 1} + a_j$가 최대가 되도록 해야 한다. 세 번째 예제에서 볼 수 있듯이 모든 수가 음수인 경우에도 최소 하나의 수를 골라야 한다. 이 문제를 DP로 풀기 위해 식을 세워 보자. $j$가 $1$인 경우부터 $n$인 경우까지 각각에 대해 해당 조건에서의 최대 연속합 $m_j$를 구하고 거기서 가장 큰 .. 163. GCD Segment Tree 연속된 원소들의 최대공약수를 빠르게 구하는 GCD 세그먼트 트리(GCD Segment Tree)에 대해 알아본다.이 세그먼트 트리의 구성 방법은 간단하다. 리프 노드에 수열의 값들을 저장하고 부모 노드에 양 자식 노드에 저장된 값의 최대공약수를 저장하는 것이다. 다음과 같은 수열이 있다고 할 때,$$a = [48, 32, 24, 36, 18, 30, 20]$$이 수열을 GCD 세그먼트 트리로 표현하면 다음과 같다.리프 노드가 빌 경우 $0$으로 채우면 된다. $x \ne 0$일 때 $\gcd(x, 0) = |x|$이므로 $20$과 $0$의 부모 노드에는 $20$이 저장된다. 또한 $\gcd(0, 0)$은 정의되지 않지만 일반적으로 그러는 것처럼 $0$으로 간주하면 된다. 이제 이 세그먼트 트리를 이용해서.. 162. Segment Tree with Lazy Propagation 다음과 같은 쿼리를 처리하는 문제를 생각해 보자.$1\ x\ y\ k$: $x$번째 수부터 $y$번째 수까지에 $k$를 더한다.$2\ x\ y$: $x$번째 수부터 $y$번째 수까지의 합을 출력한다. 만약 세그먼트 트리를 이용해서 이 쿼리를 처리하려고 한다면 $1$번 쿼리를 처리할 때 원소의 값을 바꾸는 작업을 $y - x + 1$번 실행해야 하고, 수의 개수가 $n$이라면 이 작업에는 $(y - x + 1) \lg n$만큼의 시간이 걸린다. 즉 이 시간은 바꿔야 하는 구간의 크기에 영향을 받는다. 만약 $x = 1, y = n$이라면 $1$번 쿼리 하나를 처리하는 데 $n \lg n$만큼의 시간이 걸릴 것이고 이런 쿼리가 $m$개 있다면 $nm \lg n$만큼의 시간이 걸리게 된다. 이런 시간복잡도로는.. 161. 2D Segment Tree & 2D Fenwick Tree $2$D 세그먼트 트리($2$D Segment Tree)는 세그먼트 트리를 $2$차원으로 구성한 것이다. 즉 $1$차원 세그먼트 트리들이 여러 개 존재하고 여기서 같은 위치에 있는 노드들로 구성된 세그먼트 트리들이 추가로 존재하는 방식이다. 다음과 같이 $4 \times 4$ 크기의 테이블이 존재할 때 $2$차원 세그먼트 트리를 어떻게 구성하는지 알아보자.ABCDEFGHIJKLMNOP$1$차원 세그먼트 트리를 구현할 때 $1$차원 배열을 선언했다. 비슷하게 $2$차원 세그먼트 트리를 $2$차원 배열로 구현할 것이다. 그러면 첫 번째 인덱스를 행, 두 번째 인덱스를 열에 대응해서 각 노드가 어느 범위의 데이터를 저장할지 결정할 수 있다.더보기첫 번째 인덱스로 다음과 같이 행 범위를 지정한다.$a[1][]$.. 160. Segment Tree - kth 세그먼트 트리에서 $k$번째 원소를 빠르게 찾는 방법에 대해 알아본다.다음과 같은 쿼리가 $q$개 주어지는 문제를 생각해 보자.$1\ k$: 집합에 원소 $k$를 추가한다. $k$는 $1$ 이상 $n$ 이하의 정수 중 하나이다.$2\ k$: 집합에서 $k$번째로 작은 원소를 출력한다.이 문제를 해결하는 가장 간단한 방법은 $1$번 쿼리에서 추가되는 원소를 정렬된 집합에 끼워넣는 방법과 $2$번 쿼리마다 집합을 정렬하는 방법이지만 두 방법 모두 쿼리 하나를 처리하는 시간이 $\Omega(n)$이 돼서 전체 시간복잡도는 $\Omega(nq)$로 표기할 수 있다. 물론 $n$과 $q$가 크면 속도가 너무 느려진다.세그먼트 트리는 이 문제를 $\Theta(q \lg n)$에 해결하는 방법을 제공한다. 처음에 모.. 158. Segment Tree 알고리즘 문제를 풀 때 가장 자주 등장하는 자료 구조 중 하나인 세그먼트 트리(Segment Tree)에 대해 다룬다. 먼저 누적합을 다루면서 소개했던 구간 합 구하기 4 문제를 다시 보자. 수 $n$개가 주어졌을 때, $i$번째 수부터 $j$번째 수까지 합을 구하는 프로그램을 작성하시오. 이 문제에서 주어지는 쿼리는 아래와 같다. $i\ j$: $i$번째 수부터 $j$번째 수까지의 합을 출력한다. 수의 개수 $n$과 쿼리의 개수 $m$의 최댓값이 $10^5$이므로 누적합을 전부 구한 다음 각 쿼리를 $\Theta(1)$에 처리하면 $\Theta(n + m)$에 전체 문제를 해결할 수 있었다. 이제 쿼리를 하나 더 추가하자. $1\ x\ y$: $x$번째 수를 $y$로 바꾼다. $2\ x\ y$: $x$.. 이전 1 다음
