Segment Tree

Segment Tree

특정 범위의 Array 의 Sum을 빠르게 하기 위해 만들어진 기법이다.

만약 [3,5,8,1,3,9] 라고 하는 Array가 주어 졌다고 생각해 보자.

이를 Tree로 만들면 다음과 같다.

이 Tree에서 주의해서 봐야할 점은 우측에 '0' 이다. 반듯이 Tree의 Balance를 맞춰줘야 한다.

이렇게 Tree가 만들어지면 다음과 같이 Query가 가능하다.

[3,5,8,1,3,9] 에서

• 0 ~ 5까지의 Sum은?

상기와 같이 Index 0과 5 즉

• Left Index < Right Index인 관계에서
• Left Index가 짝수이면 상위 노드로 올라간다.
• Right Index 가 홀수이면 상위 노드로 올라간다

라는 개념을 만들 수 있다.

그런데 상위 노드의 Index는 몇인가?

이를 처리하기 위해서 Root Node는 Base 1부터 하는 Array위치를 주게 된다. 다음과 같다.

[<Not use>, 29,17,12,8,9,12,0,3,5,8,1,3,9,0,0]

이 Index를 다시 그림으로 보자면 다음과 같다.

이 그림을 보면 Segment Tree의 최소 필요 Array의 양은 

• Original Array Length * 2 + 1 (1 Base Array를 만들어야 함으로 1이 필요하다)

이 된다.

계속해서 Search를 해보겠다.

여기에서 우측 6번 Index는 짝수가 됨으로 12를 저장하고 Index를 하나 줄여 줌으로써 더이상 우측 Search가 일어나지 않게 한다.

마지막으로 4번과 5번 Index를 한단계 올리면 최종적으로 2번 인덱스에서 만나게 된다.

여기서 17이라는 값을 다시 Sum에 저장하고 Node Search는 여기에서 종료한다.

답은 17 + 12인 29가 된다.

Segment Tree에서 주의 해야할 것을 정리 하자면 다음과 같다.

• 입력된 값의 Index 시작점은 0이다. Segment Tree의 위치로 보면 입력된 Array 길이 + 0이다.
  • 상위에 그림을 보면 8개를 입력하고, 사용자가 입력한 Index의 시작이 0이라는 것을 보면 된다.
• Right Index는 홀수를 기준으로 한다. 만약에 짝수 즉 Index 12가 들어온다면 Node를 위로 올라갈 필요 없이 3을 Sum에 저장하고 Node 차수를 하나 내려서 Index 11로 시작해야 한다.

이를 이용해서 만든  Segment Tree는 다음과 같다.

let SegmentTree = (function (){
    function SegmentTree(width = 100000){
        this.HOLD = width;
        this.array = new Array(width * 2 + 1).fill(0);
    };

    SegmentTree.prototype.updateIdx = function (idx, val){
        idx += this.HOLD;
        this.array[idx] = val;

        while(idx > 1){
            idx = Math.floor(idx/2);
            this.array[idx] = this.array[idx*2] + this.array[idx*2+1];
        }
    };

    SegmentTree.prototype.query = function(left, right){
        if(right == null){
            right = this.HOLD;
        }
        let sum = 0;
        let leftIdx = this.HOLD + left;
        let rightIdx = this.HOLD + right;


        while (leftIdx <= rightIdx) {
            if(leftIdx === rightIdx){
                sum += this.array[leftIdx];
                break;
            }

            if((leftIdx & 1) === 1){
                sum += this.array[leftIdx];
                leftIdx += 1;
            }

            if((rightIdx & 1) !== 1){
                sum += this.array[rightIdx];
                rightIdx -= 1;
            }

            leftIdx >>= 1;
            rightIdx >>= 1;
        }

        return sum;

    };

    return SegmentTree;

})();

이 Segment Tree는 Update시 O(LogN), Query시 O(LogN)의 속도를 갖는다.