세그먼트 트리(Segment Tree)

 

특정 구간의 합을 구할 때 사용하는 자료구조 !
- 이진 트리 형태
- 특정 구간의 합을 선형탐색(for문 등)을 통해 구하면 ≫ O(n)
- 트리의 특성 상 세그먼트 트리는 ≫ O(logN)

 

 

세그먼트 트리 구조

• 이진 트리 구조
• 다른 트리와 달리 세그먼트 트리는 인덱스가 1부터 시작
• 루트 노드에는 모든 원소를 더한 값, 각각의 노드에는 반으로 나누어 구간 합을 저장

 

세그먼트 트리 생성 과정

private int build(int[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];  // 리프 노드에 값 할당
            return tree[node]
        }
        
        int mid = (start + end) / 2;         
        return tree[node] = build(arr, 2 * node, start, mid) + build(arr, 2 * node + 1, mid + 1, end)
    }

• 재귀적으로 실행
• 두 구간으로 나누어 구간의 합을 저장함

 

세그먼트 트리로 구간 합 구하기

// 구간 합을 구하는 함수
    public int rangeSum(int L, int R) {
        return rangeSum(0, 0, n - 1, L, R);  // 루트에서 시작
    }

    // 구간 합을 구하는 재귀 함수
    private int rangeSum(int node, int start, int end, int L, int R) {
        if (R < start || end < L) {
            return 0;  // 구간 밖에 있으면 0 반환
        }
        if (L <= start && end <= R) {
            return tree[node];  // 구간 안에 완전히 포함되면 해당 구간의 합 반환
        }
        int mid = (start + end) / 2;
        int leftChild = 2 * node;
        int rightChild = 2 * node + 1;

        int leftSum = rangeSum(2 * node, start, mid, L, R);  // 왼쪽 자식
        int rightSum = rangeSum(2 * node + 1, mid + 1, end, L, R);  // 오른쪽 자식
        return leftSum + rightSum;
    }

• 범위 안에 있는 경우에만 더해주기

 

특정 원소의 값 수정

// 특정 인덱스의 값을 수정하는 함수
    public void update(int idx, int dif) {
        update(0, 0, n - 1, idx, dif);
    }

    // 값 수정 함수 (재귀)
    private void update(int node, int start, int end, int idx, int dif) {
        if(start > idx || idx > end) {
        	return;
        }
        tree[node] += dif;
        if(start == end) {
        	return;
        }
        int mid = (start + end) / 2;
        update(node*2, start, mid, idx, dif);
        update(node*2 + 1, mid + 1, end, idx, dif);
    }

• 범위 안에 있는 경우에 한에서 수정