본문 바로가기

SegTree3

Lazy Propagation Lazy Propagation 배열의 구간 쿼리, 구간 합을 빈번하게 수행할 때 비교적 적은 횟수로 쿼리를 수행하는 방법 Segment Tree, Fenwick Tree 활용의 연장선에 있다. 배열 X에서 구간 쿼리를 수행하고 구간 합을 구할 때 한 개의 트리만 사용할 경우 구간의 길이만큼 쿼리를 수행해야 한다. 이때 추가적인 트리를 사용하면 쿼리를 적은 횟수 수행하고 두 트리를 모두 사용해 구간 합을 구할 수 있다. 0으로 초기화된 배열 X에서 다음 구간 쿼리를 수행한다고 하자. [4,9]에서 +6 [3,6]에서 -2 두 세그먼트 트리/펜윅 트리 a, b를 아래와 같이 이용할 수 있게 update하자. 구간 [1,4]의 합을 구하는 경우, [1,4] 내에서 6은 X[4]에, -2는 각각 X[3], X[.. 2021. 8. 13.
KMP DP 트리 그래프 기하학 최근 푼 문제 1701 Cubeditor KMP idx(0~N-1)부터 N까지의 부분문자열에 대해 Pi를 구한다. idx에 대하여 최대 Pi값 - idx = 두 번 이상 나오는 가장 긴 부분문자열의 길이 * Pi를 구하는 시작점의 인덱스가 0이 아님에 주의해서 풀면 됨 16900 이름 정하기 KMP 주어진 문자열 S가 최소 K번 부분문자열로 등장하는 새로운 문자열 길이의 최솟값을 구한다. Pi를 구해 문자열 S에서 K-1번 반복해줄 부분 문자열을 구한다. 아래는 예시 S ada 3 pi 001 => (3-2)+2*3 S abc 2 pi 000 => (3-3)+3*2 S rr 5 pi 01 => (2-1)+1*5 S abcabcabca 3 pi 0001231234 => (10-3)+3*3 1509 팰린드롬 분할 DP 주.. 2021. 4. 16.
Segment Tree Segment Tree 세그먼트 트리 구간 별 정보를 저장하는 트리 구조로 업데이트가 빈번히 일어나거나 구간이 주어지는 쿼리문을 해결하기 좋다. 가장 유명한 예시로 구간 합이나 구간 내 최대/최솟값을 찾는 문제가 있다. 쿼리에 따라 정보를 저장하면 된다. 배열의 원소는 트리 상 리프(leaf)에 존재하며, Root를 기준으로 왼쪽과 오른쪽에 동일(하거나 한 개 차이)한 개수의 리프 정보에 대해 저장한다. N=8처럼 N=$2^n$꼴이라면 모든 노드에 대해 정확히 절반의 리프 정보를 왼쪽/오른쪽 자식 노드에 저장해 포화이진트리를 만들 수 있다. N=6, 7인 경우 아래와 같이 트리를 만든다. 아래 특징을 기억하면 된다. $n$번 노드의 왼쪽 자식 노드는 $2n$번, 오른쪽 자식 노드는 $2n+1$번이다. $.. 2021. 4. 15.

티스토리툴바