평방분할(sqrt decomposition)

구간 쿼리를 처리해야 하는 문제에서 구간 트리나 인덱스 트리를 대신해서 쓸 수 있는 방법입니다.
(따라서 구간 트리나 인덱스 트리로 풀 수 있는 문제의 대부분을 평방 분할로 풀 수 있습니다.)

핵심은 길이가 N인 배열에서 sqrt(N) 길이의 구간마다 대표값을 구해 놓는다는 것입니다.
이렇게 대표값을 구해놓으면 Q개의 구간 쿼리를 O(Q * sqrt(N))의 시간복잡도로 처리 할 수 있습니다.

관련 문제 : 

예제 : 
http://ideone.com/I7vkPa - 코드 (구간합을 다뤘지만 최소값, 최대값 등등 응용 가능합니다.)

심화 : 
Mo's Algorithm (평방 분할 + 쿼리 정렬)

댓글

댓글 쓰기

이 블로그의 인기 게시물

BOJ 11478 - 서로 다른 부분 문자열의 개수

길이 $N$인 문자열 $S$의 서로 다른 부분 문자열의 개수를 세는 문제이다. 방법 1) Suffix Array + LCP $O(NlgN)$에 해결할 수 있다. 다른 곳에서 많이 볼 수 있는 풀이이다. 방법 2) 트라이 $O(N^2)$에 해결할 수 있다. 트라이에 $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 모두 넣으면 최종적으로 트라이에 존재하는 노드의 수 - 1(루트 제외)이 답이 된다. 방법 3) 해싱 $O(N^2lgN)$에 해결할 수 있다. $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 해싱하면서 유니크한 해싱값들의 수를 세면 된다. 코드 (트라이) :  http://ideone.com/bugbDy 코드 (해싱) :  http://ideone.com/hkjw5n
계속 읽기

repeated squaring

https://www.acmicpc.net/problem/1533 최대 가중치 5인데 한 정점을 정점 다섯개로 치환하고 모든 간선의 가중치가 1인것처럼 만든다. 그런식으로 만든 인접행렬을 거듭제곱하면 답을 구할 수 있다. http://codeforces.com/problemset/problem/621/E
계속 읽기