SQRT 분해

Question

가 나는 우리 크기 SQRT의 버킷 N 인 (N)로 입력 배열을 분할하는이 DS의 표준 ALGO을 이해 https://acmcairoscience.wordpress.com/2015/04/06/sqrt-decomposition/

이 사이트 SQRT 분해 데이터 구조에 대한 판독 질의 배열의 사이즈

하지만 여기서는 이해할 수없는 것이 있습니다. 입력 쿼리의 sqrt 분해.

몇 가지 입력 데이터가 주어진 다음 몇 가지 문제가 있다고 가정하고 k 개의 쿼리를 처리하고 각각 응답해야합니다. 요청이 요청 될 때 (시스템의 상태를 변경하지 않고 일부 정보 만 묻기)와 수정 (시스템의 상태에 영향을주는 것은 초기에 입력 데이터로 설정) 인 경우를 고려합니다.

이것은 이해할 수없는 주어진 접근법입니다. sqrt (k) 크기의 버킷에서 k 개의 쿼리를 분할하고 각 버킷의 모든 쿼리를 한 번에 처리합니다.

왜 쿼리를 sqrt 크기의 버킷으로 분해합니까 ?? 각 버킷에서 모든 쿼리를 처리하는 방법은 무엇입니까 ??

Answer 1

그는 쿼리를 버킷으로 분할하지 않고 오히려 논리적으로 sqrt (k)의 버킷으로 데이터를 분할합니다. 그런 다음 수신 된 각 쿼리에 응답하지 않고 쿼리를 다시 정렬하여 범위별로 순서가 처리되도록합니다. 즉, 버킷 N에서 시작하는 쿼리는 버킷 N + 1에서 시작하는 쿼리보다 먼저 처리되고 버킷 M에서 끝나는 쿼리는 버킷 M + 1에서 끝나는 쿼리보다 먼저 처리됩니다.

따라서 쿼리는 왼쪽에서 오른쪽으로 순차적으로 처리됩니다.

sqrt (n) 버킷이있는 경우 각 버킷의 크기는 sqrt (n)입니다. q = sqrt (n)이라고합시다.

첫 번째 쿼리가 버킷 1을 사용한다고 가정 해 봅시다. 프로그램은 첫 번째 버킷에 대해 q^2 계산 을 수행해야합니다. 그런 다음 버킷 1에서 시작하는 다른 쿼리가 다시 계산할 필요가 없도록 결과를 캐시합니다. 프로그램이 왼쪽에서 오른쪽으로 쿼리를 처리 할 때 결국 각 버킷에 대해 동일한 q^2 계산을 수행해야합니다. 쿼리가 모든 버킷을 사용하여 끝나면 우리는 q^2 시간이 걸린 q 계산을 수행했습니다.

q = sqrt (n)이기 때문에, q * q^2 = sqrt (n) * n.