[세그먼트 트리]구간합, 최대, 최소

구간합, 최대, 최소 구할때?

배열 주고 한번만 구간합, 최대, 최소를 물어보면 그냥하면 됌

근데 여러번 물어본다면? 여러번을 for문에 for문을 돌리겠지.

이때 쓰는거라 함

 

구간합

1. N개 수가 있으면

var k = Math.ceil(Math.log2(v));

2. 2진트리에 맨 아래층(k+1층)에 왼쪽부터 깔고

3. 남는 부분은 0으로 채우고

var A = Array.from({length: Math.pow(2,k+1)}, () => 0);
for (var i=0;i<arr.length;i++) {
    A[Math.pow(2,k)+i] = arr[i];
}

4. 부모노드에 자식노드의 합(또는 최대, 최소)으로 채움

for (var i=Math.pow(2,k)-1;i>=1;i--) {
    A[i] = A[2*i] + A[2*i+1];
}

5. 루트노트를 배열의 index=1로 시작해서 배열로 만듬

6. 구간합을 위한 start, end 인덱스가 정해지면

7. start가 형제노드들 중에 왼쪽인지 오른쪽인지 판단

8. start가 오른쪽이면 sum에 더하고 start+1

9. end가 왼쪽이면 sum에 더라고 end+1

10. start와 end사이는 부모노드를 타고 가면서 더하는데

11. start의 부모노드는 /2

12. end의 부모노드도 /2

7~12과정을 start<=end 일 경우만 반복

 

function sum(start, end) {
    var sum = 0;
    start += Math.pow(2,k)-1;
    end += Math.pow(2,k)-1;
    while (start <= end) {
        if (start % 2 == 1) {
            sum += A[start];
            start++;
        }
        if (end % 2 == 0) {
            sum += A[end];
            end--;
        }
        start /= 2;
        end /= 2;
    }
    return sum;
}

 

최소

var max = Math.max(...arr);
var k = Math.ceil(Math.log2(v));
var A = Array.from({length: Math.pow(2,k+1)}, () => max);

for (var i=0;i<arr.length;i++) {
    A[Math.pow(2,k)+i] = arr[i];
}

for (var i=Math.pow(2,k)-1;i>=1;i--) {
    A[i] = Math.min(A[2*i],A[2*i+1]);
}

function min(start, end) {
    start += Math.pow(2,k)-1;
    end += Math.pow(2,k)-1;
    var min = A[start];
    while (start <= end) {
        if (start % 2 == 1) {
            min = Math.min(min,A[start]);
            start++;
        }
        if (end % 2 == 0) {
            min = Math.min(min,A[end]);
            end--;
        }
        start /= 2;
        end /= 2;
    }
    return min;
}