반응형 sqrt decomposition 자료구조1 [C++] Sqrt Decomposition 알고리즘 Sqrt Decomposition 알고리즘은 연속된 어떤 배열을 구간 별로 합을 bucket에 저장하여 효과적으로 구간합을 구할 수 있는 알고리즘이다. 주로 어디서 부터 어디까지 합을 구해야하는 문제에서 요긴하게 쓸 수 있다. 시간복잡도는 O( √n)으로, 보다 빠른 방법은 Segment tree 알고리즘이 있지만, Sqrt Decomposition이 상대적으로 구현하기 쉽고 Segment tree로 풀 수 없는 문제도 풀 수 있으니 꼭 알아두자. 예제로 백준 2042번: 구간 합 구하기를 풀어보자.#include #include #define MAX 1'000'001using namespace std;typedef long long ll;ll N, M, K;ll Numbers[MAX];ll Bucket.. 2024. 6. 28. 이전 1 다음 반응형
