[Algorithm] 구간 질의

합 질의와 최소 질의는 특정 배열 구간이 주어졌을 때 구간의 합 혹은 구간에서 존재하는 최소 값을 뽑아내는 알고리즘이다.

1. 구간 합 질의

보통 구간 합의 구할 때

array[5] = {5, 4, 3, 2, 1}

이라고하면 sum(2,4)는 4+3+2로 9라는 답변을 받게 된다.

이처럼 인덱스 구간의 합을 구하는 function이다.

 

그때 그때 구하게되면 반복되는 덧셈으로 인하여 효율성이 많이 떨어진다. 때문에 이 경우 누적 합 배열을 하나로 더 만들고

SumArray[5] = {5, 9, 12, 14, 15}

여기서 sum(2,4)인 경우 SumArray[3]-SumArray[0]로 구할 수 있다.

 

14 - 5 = 9 로 동일한 답변을 얻게 된다.

 

이 경우 덧셈을 처음 누적 배열을 만들 때 1회만 하므로 높은 시간 효율성을 가질 수 있다.

 

Sum(A,B) = Sum(0,B)-Sum(0,A-1)

 

 

 

2. 최솟값 질의

최솟값 질의 방법은 2의 거듭 제곱 수로 구간의 길이를 늘려가며 최솟값을 미리 구하는 배열을 만드는 방법으로 해결이 가능하다.

array = {5, 4, 3, 2, 1}

이라고 했을 때 2의 거듭제곱으로 구간의 길이가 1인경우, 2인경우, 4인경우 8인경우의 배열을 만들어서 문제를 해결할 수 있다.

 

구간이 1인경우 {5, 4, 3, 2, 1} 구간이 2인 경우 {4, 3, 2, 1, 1} 구간이 4인 경우 {2, 1, 1, 1, 1} 구간이 8인 경우 {1, 1, 1, 1, 1}

이렇게 2의 거듭제곱으로 배열들을 구하고 min(a,b)에 대하여 a와 b사이에 존재하는 2의 거듭제곱수를 기준으로 min(a,2의 거듭제곱)과 min(2의거듭제곱, b)의 값들을 구해 둘 중 더 작은 값을 리턴함으로써 해결할 수 있다.

 

 

3. 이진 인덱스 트리(펜윅 트리)

해당 기법은 구간 합 질의와 같은 내용으로 구간합을 구하는 알고리즘이다.

위에서 언급한 구간 합 알고리즘의 경우 만약 SumArray[]를 모두 구했는데 인덱스 값이 하나가 변경이된다면?

이 경우 O(n)의 작업을 다시 진행해야만 한다.

 

하지만 펜윅트리는 다르다. 2의 거듭제곱을이용한 해당방법을 이용하면 update에 시간을 O(logN)으로 최소화가 가능하다.

원리는 아래와 같다.

bit값중 LSB로부터 시작해서 처음으로 '1' bit를 가지는 값까지 누적을 진행하는 방법이다.

 

출저 https://velog.io/@ybw903/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%B4%EC%A7%84-%EC%9D%B8%EB%8D%B1%EC%8A%A4-%ED%8A%B8%EB%A6%AC%ED%8E%9C%EC%9C%85-%ED%8A%B8%EB%A6%AC

 

 

위와 같이

Array = { 1, 2, 0, 4, 1, 3, 5, 9, 8, 6}

라고하고 펜윅트리를 이용해서 구간 합 질의를하기위해 SumArray를 만들면 아래와 같은 방법을 이용한다.

여기서 첫 index는 1이라 하며, LSB부터 시작하여 처음 '1'bit를 구하는 function을 이하 LSB라 한다.

LSB(1) = 0b1이므로 1이된다.

LSB(2) = 0b10 이므로 2가된다.

LSB(3) = ob11 이므로 1이된다.

 

먼저 Array맨 끝 index부터 거꾸로 진행한다.

Array 마지막 인덱스는 index 10이다. LSB(10) = 2

값이 2이므로 자신의 index부터 거꾸로 길이 2만큼 합한 값을 가지게된다.

SumArray = { x, x, x, x, x, x, x, x, x, 14}가 된다.

 

LSB(9) = 1 SumArray = { x, x, x, x, x, x, x, x, 8, 14}가 된다. LSB(8) = 8 SumArray = { x, x, x, x, x, x, x, 25, 8, 14}가 된다. LSB(7) = 1 SumArray = { x, x, x, x, x, x, 5, 25, 8, 14}가 된다. … LSB(2) = 2 SumArray = { x, 3, 0, 7, 1, 4, 5, 25, 8, 14}가 된다. LSB(1) = 1 SumArray = { 1, 3, 0, 7, 1, 4, 5, 25, 8, 14}가 된다.

 

그리고 위와 같이 만들어진 SumArrary의 index값이 바뀌게 된다면 아래와 같이 빠르게 update가 가능하다.

index 3 의 값이 0에서 5로 변경되었다면 증가되는 크기(5)를 찾고 증가된 값을 이용한다. (0->5 이므로 5만큼 증가되었으므로 5를 이용)

Array = { 1, 2, 5, 4, 1, 3, 5, 9, 8, 6}

 

SumArray[3] += 5 해주고 LSB(3) = 1이므로 길이를 1만큼 증가시켜

SumArray[4] += 5 해주고 LSB(4) = 4이므로 길이를 4만큼 증가시켜

SumArray[8] += 5를 해준다.

 

이렇게만 해주면 수정이 바로 진행된다.

 

 

 

4. 구간 트리

마지막으로 구간 트리를 이용하는 방법은 이진 트리 형태를 이용하여 Node의 값이 Left child + Right child를 하게끔하여 구간 질의를 진행하는 방법이다.

 

https://reakwon.tistory.com/44

위와 같이 Array가 가장 아래 Leaf노드에 깔리게되고 Leaf Node의 parent노드가 각각 index끼리의 합이되고 또 parent의 parent가 parent들끼리의 합이되면서 트리를 만드는 구조이다.

 

해당 방법을 이용하면 인덱스가 홀수인지 짝수인지를 바탕으로 자신이 parent기준 left child인지 right child인지 찾고 parent로 index/2를해가며 올라가서 구간질의상 할 수 있는 가장 높은 Level의 Node의 값을 이용해서 구간 질의를 진행하는 방법이다.

 

이 방법역시 update진행 시에 index/2로 parent로 올려주면서 수정만 하면되기 때문에 O(logN)의 좋은 성능을 낼 수 있다.

구간 질의는 Sum뿐만 아니라 최소 질의 등으로도 사용할 수 있다. 그 외에도 이전 인덱스 값과 현재 인덱스 값의 차이를 나타내는 등 다양한 활용 가능