juhyun16   5년 전

  1. 구간의 최소값을 구하는 연산
  2. 하나의 값을 업데이트하는 연산

위의 두 연산을 빠르게 할 수 있는 자료구조가 있는지 궁금합니다....

그런데 1번 최소값을 구하는 연산에서 구간이 step을 가진다면........... 좀 더 구체적인 예를 들어보도록 하겠습니다.

배열 arr [0] ~ [N-1] 에 int 값이 저장되어 있다고 가정해보겠습니다.

arr[10], arr[11], arr[12], arr[13], ..., arr[99], arr[100] 중 최소값을 구하는 건 segment tree를 이용하면 빨리 할 수 있는 것으로 알고 있습니다.

  •  arr[10], arr[20], arr[30], ... , arr[90], arr[100] 중 최소값 구하기
  •  arr[20], arr[40], arr[60], ... , arr[80], arr[100] 중 최소값 구하기
  •  arr[2], arr[5], arr[8], arr[11], arr[14], arr[17], arr[20], arr[23], arr[26] 중 최소값 구하기
  •  arr[30]의 값을 업데이트 하기
  •  arr[29]의 값을 업데이트 하기
  •  arr[25]의 값을 업데이트 하기 
  • ...

이와 같은 연산을 빠르게 처리할 수 있는 자료구조가 있는지 궁금합니다.

portableangel   5년 전

step < sqrt(N)일 때와, step >= sqrt(N)일 때로 나누어 풀면

  1. step > sqrt(N) : 직접 모든 수를 다 조사한다. O(sqrt(N))
  2. step <= sqrt(N) : 모든 K <= sqrt(N) 에 대해, 각 K로 나누었을 때 나머지가 0, 1, 2, ... , K-1인 인덱스에 해당하는 트리를 전부 만들어둔다. 메모리 사용량은 1부터 sqrt(N)까지 각각의 mod K 트리가 합산 1+2+...+K의 사이즈를 가지므로 대략 O(Nsqrt(N))이 된다. 이제, 이 트리를 참조하여 문제를 해결할 수 있다. 예를 들어, arr[4], arr[7], arr[10], ... , arr[31] 중 최소값을 구하는 경우, mod 3 = 1인 트리에서 두번째 원소부터 11번째 원소까지의 최소값을 찾으면 된다. 
  3. 업데이트는 해당 원소를 포함하는 많아야 sqrt(N)개의 트리에 직접 해준다. ( idx를 업데이트 한다면, idx mod 1, mod 2, ... , mod sqrt(N) 에 해당하는 트리를 건드리면 된다.)

이렇게 해서 우선은 O(Nsqrt(N)log(N))에 모든 쿼리를 해결할수 있을것 같은데, 더 빠른 방법은 아래의 누군가가 제시해주실 것 같습니다.

juhyun16   5년 전

빠른 답변 감사합니다~ 혹시 말씀해주신 개념을 사용해서 풀 수 있는 연습문제가 있을까요?

어떤 온라인저지이건 괜찮습니다. 문제를 한번 풀어보고 싶네요. 혹 알고 계시면 답변해주시면 감사하겠습니다.

댓글을 작성하려면 로그인해야 합니다.