[Algorithm] 세그먼트 트리(Segment Tree)를 Java로 구현해보자! !(with BOJ-2042 Java로 문제풀이)

---

안녕하세요 Coding-Knowjam입니다.

오늘은 세그먼트 트리를 Java로 구현해보도록 하겠습니다.

 

1. 세그먼트 트리 (Segment Tree)

세그먼트 트리는 이름에서도 나타나듯이 트리 형태의 자료구조를 사용합니다.

숫자가 저장된 배열이 존재할 때 해당 배열의 구간 합을 구하거나, 배열의 특정 인덱스의 값을 변경한 후에 다시 구간합을 구해야 한다면 세그먼트 트리를 사용하는 것이 시간 복잡도 측면에서 적합합니다.

세그먼트 트리에 대한 이론적인 설명은 백준 온라인 저지에 있는 게시물에 명쾌하게 정리가 되어있습니다.

그러므로 해당 게시글을 꼭 읽어보시길 바라며 세그먼트 트리가 무엇인지는 대충 아신다는 전제하에 Java로 코드를 구현해보겠습니다.

구현 코드는 예제를 들어서 해도 되지만 백준 온라인 저지에 세그먼트 트리에 딱 맞는 문제가 있기 때문에 해당 문제를 풀어보면서 코드를 같이 설명드리겠습니다.

게시글과 문제 링크는 아래를 참고해주세요.

(게시글 : https://www.acmicpc.net/blog/view/9)

(문제 : https://www.acmicpc.net/problem/2042)

 

2. Java 코드로 세그먼트 트리(Segment Tree) 구현

백준 온라인 저지에 있는 세그먼트 트리 게시글에서는 별도의 클래스를 생성해서 코드를 설명하고 있지 않지만, 저는 별도의 세그먼트 트리 클래스를 만들어서 구현을 해보도록 하겠습니다.

2.1 세그먼트 트리(Segment Tree) 클래스 생성

static class SegmentTree{
        // 세그먼트 트리를 구현할 배열
        private long[] tree;
}

클래스에 static이 붙은 이유는 main메서드 안에서 사용할 클래스이기 때문입니다.

세그먼트 트리는 이진트리의 형태를 가지기 때문에 배열로 구현할 수 있습니다.

문제에서 주어지는 배열에 저장되는 수의 범위가 int타입의 범위를 넘어서기 때문에 long타입의 배열을 SegmentTree클래스 내부에 선언해줍니다.

 

2.2 세그먼트 트리(Segment Tree) 초기화 메서드 작성

static class SegmentTree{
        // 세그먼트 트리를 구현할 배열
        private long[] tree;

        // 생성자에서 세그먼트 트리의 전체노드 수 계산 (즉, 배열 길이)
        SegmentTree(int n) {
            // 트리의 높이 계산
            double treeHeight = Math.ceil(Math.log(n)/Math.log(2))+1;
            // 트리의 노드 수 계산
            long treeNodeCount = Math.round(Math.pow(2, treeHeight));
            // 트리의 길이 설정
            tree = new long[Math.toIntExact(treeNodeCount)];
        }

        // 세그먼트 트리의 노드 값 초기화
        long init(long[] arr, int node, int start, int end ){
            // 세그먼트 트리의 리프노드인 경우
            if (start == end) {
                // 리프노드에 배열의 값 저장 후 리턴
                return tree[node] = arr[start];
            }else{
                // 리프노드가 아닌 경우에는 자식노드의 값을 더해서 노드의 값 초기화 후 리턴
                return tree[node] = init(arr, node*2, start, (start+end)/2) 
                                  + init(arr, node*2+1, (start+end)/2+1, end);
            }
        }
}

세그먼트 트리(Segment Tree)에 값을 저장하는 초기화 작업 전에 우선 생성자부터 작성해줍니다.

세그먼트 트리에서 사용하는 노드의 개수를 따로 계산해서 초기화 메서드에 넣어 줄 수도 있지만 저는 클래스가 생성될 때 계산되도록 구현했습니다.

생성자에서 받는 파라미터는 배열의 길이를 주면 됩니다.

세그먼트 트리 구현에 사용할 내부 배열의 길이는 노드의 전체 개수가 되며, 이를 구하는 공식은 다음과 같습니다.

세그먼트 트리의 높이 = logN(밑이 2인 로그)의 값을 올림 한 후 + 1

세그먼트 트리의 전체 노드 수 = 2^(트리의 높이)

로그의 값을 올림 처리하지 않고 계산을 하게 되면 필요한 노드의 개수보다 값이 적게 계산되어 Exception이 발생합니다.

로그의 값을 올림 처리해서 계산하면 필요한 노드의 개수보다 값이 크게 나올 수 있습니다.

이러한 경우 배열에서 사용하지 않는 인덱스들이 존재하지만 메모리에 크게 영향을 주지는 않는 부분이므로 무방합니다.

세그먼트 트리(SegmentTree)의 생성이 끝났으면 트리의 노드에 초기 값을 저장할 수 있도록 초기화 메서드를 작성해줍니다.

세그먼트 트리(SegmentTree)의 초기화 작업은 재귀 메서드를 통해서 구현할 수 있습니다.

부모 노드의 값은 자식 노드의 값을 더해서 표현할 수 있습니다.

init메서드의 파라미터는 다음과 같은 의미를 가집니다.

long[] arr : 세그먼트 트리(Segment Tree)로 나타낼 배열 (세그먼트 트리는 리프 노드에 배열의 값을 저장합니다.)

int node : 메서드를 시작할 노드 인덱스 (항상 1번 인덱스부터 시작합니다.)

int start : 세그먼트 트리(Segment Tree)의 노드들이 가지는 값의 시작 인덱스입니다.

int end : 세그먼트 트리(Segment Tree)의 노드들이 가지는 값의 종료 인덱스입니다.

세그먼트 트리(Segment Tree)의 각각의 노드들(리프 노드 제외)은 모두 배열의 특정 구간의 합을 의미합니다.

예를 들어 문제에서 주어진 배열의 길이가 15라면 1번 노드는 0~14 인덱스의 합, 2번 노드는 0~7까지 3번 노드는 8~14까지 이런 식으로 각각의 노드들이 가지는 값은 배열의 특정 구간의 합을 의미합니다.

즉, start와 end 파라미터는 노드가 가지는 값의 시작과 종료 인덱스를 의미한다고 생각하시면 됩니다.

이제 init메서드를 통해 1번 노드부터 진행을 하면 재귀 형태로 리프 노드에 도달할 때까지 계속 호출되다가 리프 노드에 도달하면 노드가 가지는 인덱스를 통해 배열에서 값을 찾고 이를 노드에 저장 후 리턴합니다.

값이 리턴되면 재귀 형태로 호출되었던 함수들이 종료되면서 차례로 각각의 노드들에 값이 저장됩니다.

그리고 추가적으로 배열에서 자식 노드의 노드 번호는 다음과 같이 구할 수 있습니다.

자식 노드 번호 (좌측) = 부모 노드 번호 * 2

자식 노드 번호 (우측) = (부모 노드 번호 * 2) +1

 

2.3 세그먼트 트리(Segment Tree)에서 특정 구간의 합 구하는 메서드 작성

세그먼트 트리(Segment Tree)를 생성하고 초기 값 설정까지 끝났으면 배열이 특정 구간의 합을 구하는 메서드를 작성해보도록 하겠습니다.

// 배열의 특정 구간 합을 세그먼트 트리로 구하기
long sum(int node, int start, int end, int left, int right) {
    // 노드가 가지는 값의 구간이 구하려고 하는 합의 구간에 속하지 않는 경우 0리턴
    if (end < left || right < start) {
        return 0;
    } else if (left <= start && end <= right) {
    // 노드가 가지는 값의 구간이 구하려고 하는 합의 구간에 속하는 경우 노드 값 리턴
        return tree[node];
    } else {
    // 그 외는 2가지 경우가 존재
    // 1. 노드가 가지는 값의 구간이 구하려고 하는 합의 구간에 일부는 속하고 일부는 속하지 않는 경우
    // 2. 노드가 가지는 값의 구간이 구하려고 하는 합의 구간을 모두 포함하는 경우
    // 이와 같은 경우에는 자식노드를 탐색해서 값을 리턴
        return sum(node*2, start, (start+end)/2, left, right)
             + sum(node*2+1, (start+end)/2+1, end, left, right);
    }
}

sum메서드의 파라미터는 다음과 같은 의미입니다.

int node : 세그먼트 트리(Segment Tree)의 노드 번호

int start : 노드가 가지는 합의 시작 인덱스

int end : 노드가 가지는 합의 끝 인덱스

int left : 구하려고 하는 배열의 구간 합 중 구간의 시작 인덱스

int right : 구하려고 하는 배열의 구간 합 중 구간의 끝 인덱스

 

세그먼트 트리(Segment Tree)에서 배열의 특정 구간의 합을 구하기 위해서는 4가지의 경우를 구분해서 생각해야 합니다.

1. 노드가 가지는 구간이 구하려고 하는 배열의 구간에 포함되지 않은 경우 -> 0 리턴

2. 노드가 가지는 구간이 구하려고 하는 배열의 구간에 포함되거나 같은 경우 -> 노드 값 리턴

3. 노드가 가지는 구간이 구하려고 하는 배열의 구간을 모두 포함하고 있는 경우 -> 자식 노드로 이동

4. 노드가 가지는 구간이 구하려고 하는 배열의 구간에 일부는 포함 일부는 미포함인 경우 -> 자식 노드로 이동

세그먼트 트리(Segment Tree)의 리프 노드를 제외한 노드의 값은 자식 노드의 합인 점을 이용해서 재귀 형태로 메서드를 작성해주었습니다.

3, 4번의 경우 계속해서 재귀 형태로 1,2번의 경우에 도달할 때까지 자식 노드를 호출합니다.

1,2번의 경우에 도달하면 값을 리턴하고 메서드가 종료됩니다.

재귀 형태로 호출되었던 메서드들도 차례대로 종료되면서 특정 구간의 합을 구할 수 있습니다.

 

2.4 세그먼트 트리(Segment Tree)에서 배열의 특정 인덱스 값을 변경하는 메서드 작성

앞서 배열의 특정 구간에 대해서 합을 구하는 메서드까지 코드로 구현해보았습니다.

이제 배열의 특정 인덱스의 값을 변경하는 메서드를 작성하겠습니다.

세그먼트 트리(Segment Tree)는 부모 노드의 값을 자식 노드의 합으로 표현할 수 있습니다.

그러므로 배열의 각각의 원소에 해당하는 리프 노드의 값이 바뀌게 된다면 해당 리프 노드의 부모 노드의 값 또한 바뀌어야 하고 그 부모 노드의 부모 노드 또한 바뀌어야 합니다.

처음에 읽어보시길 권했던 백준 온라인 저지에 있는 게시글에서는 변경할 값 - 기존 값 = 차이 값을 이용해서 변경되어야 할 모든 노드들에 차이 값을 더해주는 식으로 세그먼트 트리(Segment Tree)의 값을 변경해주고 있습니다.

또 다른 방법은 먼저 리프 노드의 값을 변경하고자 하는 값으로 바꾸고, 부모 노드들의 값은 자식 노드들의 값을 더해서 구하는 식으로 세그먼트 트리(Segment Tree)의 값을 변경하는 방법도 있습니다.

2가지 방법에 대해서 모두 코드로 구현해보겠습니다.

// 배열의 특정 인데스의 값이 변경 될 경우 세그먼트 트리의 노드 값 변경(차이 값을 더하는 방법)
void update(int node, int start, int end, int index, long diff) {
    // 노드가 가지는 값의 구간에 배열의 인덱스(값이 변경 될 인덱스)가 포함되지 않을 경우
    if (index < start || end < index) {
        // 아무것도 안함
        return;
    }else {
        // 노드가 가지는 값의 구간에 배열의 인덱스(값이 변경 될 인덱스)가 포함되는 경우
        // 노드의 값 + 차이값(변경할 값-기존값)
        tree[node] = tree[node] + diff;                                                                  

        // 노드가 리프노드가 아닌 경우
        if (start != end) {
            // 리프노드까지 계속 자식노드를 탐색
            update(node*2, start, (start+end)/2, index, diff) ;
            update(node*2+1, (start+end)/2+1, end, index, diff) ;
        }
    }
}

// 배열의 특정 인데스의 값이 변경 될 경우 세그먼트 트리의 노드 값 변경(노드 값을 직접 변경)
long update2(int node, int start, int end, int index, long changeValue) {
    // 노드가 가지는 값의 구간에 배열의 인덱스(값이 변경 될 인덱스)가 포함되지 않을 경우
    if (index < start || end < index) {
        // 트리의 노드 값 리턴
        return tree[node];
    } else if (start == index && end == index) {
        // 노드가 가지는 값의 구간과 배열의 인덱스(값이 변경 될 인덱스)값이 같은 경우
        // 노드의 값을 변경 될 값으로 변경
        return tree[node] = changeValue;
    } else {
        // 노드가 가지는 값의 구간에 배열의 인덱스(값이 변경 될 인덱스)값이 포함되는 경우(같은 경우는 제외)
        // 자식 노드를 탐색 후 값을 더해서 리턴
        return tree[node] = update2(node * 2, start, (start + end) / 2, index, changeValue) +
                update2(node * 2 + 1, (start + end) / 2 + 1, end, index, changeValue);
    }
}

update메서드의 파라미터는 다음과 같은 의미를 가집니다.

int node : 메서드가 실행되는 노드의 번호

int start : 노드가 가지는 합의 시작 인덱스

int end : 노드가 가지는 합의 끝 인덱스

int index : 값이 변경될 배열의 인덱스

long diff : 변경될 값 - 배열의 기존 값 = 차이 값

위에서 설명했던 것처럼 차이 값을 구해서 각각의 노드가 가지는 구간에 변경될 배열의 인덱스가 포함되면 차이 값을 더하는 식으로 변경해주고, 이와 같은 과정을 리프 노드에 도달할 때까지 재귀 형태로 메서드가 진행됩니다.

 

또 다른 방법인 update2 메서드의 파라미터는 다음과 같은 의미를 가집니다.

int node : 메서드가 실행되는 노드의 번호

int start : 노드가 가지는 합의 시작 인덱스

int end : 노드가 가지는 합의 끝 인덱스

int index : 값이 변경될 배열의 인덱스

long changeValue : 변경될 값

메서드의 진행은 우선적으로 리프 노드에 도달할 때까지 메서드를 재귀 호출합니다.

리프 노드에 도달하면 변경될 값으로 변경해주고 리프 노드의 값을 리턴해줍니다.

노드가 가지는 구간에 해당 인덱스가 포함되지 않으면 값의 변경이 일어나지 않으므로 노드 값을 바로 리턴해줍니다.

이후에는 재귀 형태의 호출로 인해 각각의 노드 값들이 자식 노드들의 합으로 변경되면서 세그먼트 트리가 갱신됩니다.

 

2.5 세그먼트 트리(Segment Tree) 전체 코드

세그먼트 트리(Segment Tree)를 구현한 전체 코드는 다음과 같습니다.

static class SegmentTree{
        // 세그먼트 트리를 구현할 배열
        private long[] tree;

        // 생성자에서 세그먼트 트리의 전체노드 수 계산 (즉, 배열 길이)
        SegmentTree(int n) {
            // 트리의 높이 계산
            double treeHeight = Math.ceil(Math.log(n)/Math.log(2))+1;
            // 트리의 노드 수 계산
            long treeNodeCount = Math.round(Math.pow(2, treeHeight));
            // 트리의 길이 설정
            tree = new long[Math.toIntExact(treeNodeCount)];
        }

        // 세그먼트 트리의 노드 값 초기화
        long init(long[] arr, int node, int start, int end ){
            // 세그먼트 트리의 리프노드인 경우
            if (start == end) {
                // 리프노드에 배열의 값 저장 후 리턴
                return tree[node] = arr[start];
            }else{
                // 리프노드가 아닌 경우에는 자식노드의 값을 더해서 노드의 값 초기화 후 리턴
                return tree[node] = init(arr, node*2, start, (start+end)/2)
                        + init(arr, node*2+1, (start+end)/2+1, end);
            }
        }

        // 배열의 특정 구간 합을 세그먼트 트리로 구하기
        long sum(int node, int start, int end, int left, int right) {
            // 노드가 가지는 값의 구간이 구하려고 하는 합의 구간에 속하지 않는 경우 0리턴
            if (end < left || right < start) {
                return 0;
            } else if (left <= start && end <= right) {
                // 노드가 가지는 값의 구간이 구하려고 하는 합의 구간에 속하는 경우 노드 값 리턴
                return tree[node];
            } else {
                // 그 외는 2가지 경우가 존재
                // 1. 노드가 가지는 값의 구간이 구하려고 하는 합의 구간에 일부는 속하고 일부는 속하지 않는 경우
                // 2. 노드가 가지는 값의 구간이 구하려고 하는 합의 구간을 모두 포함하는 경우
                // 이와 같은 경우에는 자식노드를 탐색해서 값을 리턴
                return sum(node*2, start, (start+end)/2, left, right)
                        + sum(node*2+1, (start+end)/2+1, end, left, right);
            }
        }

        // 배열의 특정 인데스의 값이 변경 될 경우 세그먼트 트리의 노드 값 변경(차이 값을 더하는 방법)
        void update(int node, int start, int end, int index, long diff) {
            // 노드가 가지는 값의 구간에 배열의 인덱스(값이 변경 될 인덱스)가 포함되지 않을 경우7
            if (index < start || end < index) {
                // 아무것도 안함
                return;
            }else {
                // 노드가 가지는 값의 구간에 배열의 인덱스(값이 변경 될 인덱스)가 포함되는 경우
                // 노드의 값 + 차이값(변경할 값-기존값)
                tree[node] = tree[node] + diff;

                // 노드가 리프노드가 아닌 경우
                if (start != end) {
                    // 리프노드까지 계속 자식노드를 탐색
                    update(node*2, start, (start+end)/2, index, diff) ;
                    update(node*2+1, (start+end)/2+1, end, index, diff) ;
                }
            }
        }

        // 배열의 특정 인데스의 값이 변경 될 경우 세그먼트 트리의 노드 값 변경(노드 값을 직접 변경)
        long update2(int node, int start, int end, int index, long changeValue) {
            // 노드가 가지는 값의 구간에 배열의 인덱스(값이 변경 될 인덱스)가 포함되지 않을 경우
            if (index < start || end < index) {
                // 트리의 노드 값 리턴
                return tree[node];
            } else if (start == index && end == index) {
                // 노드가 가지는 값의 구간과 배열의 인덱스(값이 변경 될 인덱스)값이 같은 경우
                // 노드의 값을 변경 될 값으로 변경
                return tree[node] = changeValue;
            } else {
                // 노드가 가지는 값의 구간에 배열의 인덱스(값이 변경 될 인덱스)값이 포함되는 경우(같은 경우는 제외)
                // 자식 노드를 탐색 후 값을 더해서 리턴
                return tree[node] = update2(node * 2, start, (start + end) / 2, index, changeValue) +
                        update2(node * 2 + 1, (start + end) / 2 + 1, end, index, changeValue);
            }
        }
    }

 

3. BOJ-2043 Java로 문제풀이

앞서 구현했던 코드와 함께 실제 문제를 풀어보겠습니다.

문제에 대한 링크는 맨 처음에 적어드렸으니 읽고 오시길 바라겠습니다.

해당 문제에서 주어지는 조건은 배열이 0 인덱스가 아닌 1 인덱스부터 시작하는 형태로 조건을 주고 있습니다.

코드를 구현할 때 인덱스 관련 부분에서 -1을 해주면 되지만 이해를 조금 더 쉽게 하기 위해 배열을 생성할 때 길이에 +1을 해주었습니다.

세그먼트 트리(Segment Tree)의 업데이트 관련 메서드는 2가지가 있는데 일부러 주석 처리하지 않았으니 이점 참고해서 문제풀이 하시길 바랍니다. (해당 코드 그대로 제출하면 시간 초과 판정받을 수도 있습니다)

그 외의 코드에 대해서는 라인별로 모두 주석을 달아놓았으니 이해하시는데 어렵지 않을 거라 생각합니다.

package study.blog.codingnojam.algorithm;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BOJ_2042 {

    public static void main(String[] args) throws IOException {
        // 입출력을 위한 변수
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 문제풀이를 위한 기본 정보 받기
        String[] info = br.readLine().split(" ");

        // 배열 변수 선언 (배열의 0인덱스는 안 쓸려고 길이 1추가)
        long[] arr = new long[Integer.parseInt(info[0])+1];

        // 배열 값 초기화
        for (int i = 1; i <= Integer.parseInt(info[0]); i++) {
            arr[i] = Long.parseLong(br.readLine());
        }

        // 세그먼트 트리 생성
        SegmentTree st = new SegmentTree(Integer.parseInt(info[0]));
        // 세그먼트 트리 값 초기화
        st.init(arr, 1, 1, Integer.parseInt(info[0]));

        // 문제에서 주어진 구간 합, 특정 인덱스 값 변경 작업의 횟수만큼 반복
        for (int i = 0; i < Integer.parseInt(info[1]) + Integer.parseInt(info[2]); i++) {
            String[] operation = br.readLine().split(" ");

            // 배열의 특정 인덱스의 값을 변경하는 경우
            if(Integer.parseInt(operation[0]) == 1){
                // 세그먼트 트리의 노드 값을 변경하는 2가지의 방법
                // 1. 기존 값과 변경할 값의 차이를 구해서 트리의 노드 값 변경
                long diff = Long.parseLong(operation[2]) - arr[Integer.parseInt(operation[1])];
                arr[Integer.parseInt(operation[1])] = Long.parseLong(operation[2]);
                st.update(1, 1, Integer.parseInt(info[0]), Integer.parseInt(operation[1]), diff );

                // 2. 변경할 값만 가지고 트리의 노드 값 변경
                st.update2(1, 1, Integer.parseInt(info[0]), Integer.parseInt(operation[1]), Long.parseLong(operation[2]));
            }else{
                // 배열의 특정 구간 합 구하기
                long result = st.sum(1, 1, Integer.parseInt(info[0]), Integer.parseInt(operation[1]), Integer.parseInt(operation[2]));

                // 문제에서 주어진 조건에 맞게 출력할 값 저장
                bw.write(String.valueOf(result));
                bw.newLine();
            }
        }

        // 값 출력
        br.close();
        bw.flush();
        bw.close();

    }

    static class SegmentTree{
        // 세그먼트 트리를 구현할 배열
        private long[] tree;

        // 생성자에서 세그먼트 트리의 전체노드 수 계산 (즉, 배열 길이)
        SegmentTree(int n) {
            // 트리의 높이 계산
            double treeHeight = Math.ceil(Math.log(n)/Math.log(2))+1;
            // 트리의 노드 수 계산
            long treeNodeCount = Math.round(Math.pow(2, treeHeight));
            // 트리의 길이 설정
            tree = new long[Math.toIntExact(treeNodeCount)];
        }

        // 세그먼트 트리의 노드 값 초기화
        long init(long[] arr, int node, int start, int end ){
            // 세그먼트 트리의 리프노드인 경우
            if (start == end) {
                // 리프노드에 배열의 값 저장 후 리턴
                return tree[node] = arr[start];
            }else{
                // 리프노드가 아닌 경우에는 자식노드의 값을 더해서 노드의 값 초기화 후 리턴
                return tree[node] = init(arr, node*2, start, (start+end)/2)
                        + init(arr, node*2+1, (start+end)/2+1, end);
            }
        }

        // 배열의 특정 구간 합을 세그먼트 트리로 구하기
        long sum(int node, int start, int end, int left, int right) {
            // 노드가 가지는 값의 구간이 구하려고 하는 합의 구간에 속하지 않는 경우 0리턴
            if (end < left || right < start) {
                return 0;
            } else if (left <= start && end <= right) {
                // 노드가 가지는 값의 구간이 구하려고 하는 합의 구간에 속하는 경우 노드 값 리턴
                return tree[node];
            } else {
                // 그 외는 2가지 경우가 존재
                // 1. 노드가 가지는 값의 구간이 구하려고 하는 합의 구간에 일부는 속하고 일부는 속하지 않는 경우
                // 2. 노드가 가지는 값의 구간이 구하려고 하는 합의 구간을 모두 포함하는 경우
                // 이와 같은 경우에는 자식노드를 탐색해서 값을 리턴
                return sum(node*2, start, (start+end)/2, left, right)
                        + sum(node*2+1, (start+end)/2+1, end, left, right);
            }
        }

        // 배열의 특정 인데스의 값이 변경 될 경우 세그먼트 트리의 노드 값 변경(차이 값을 더하는 방법)
        void update(int node, int start, int end, int index, long diff) {
            // 노드가 가지는 값의 구간에 배열의 인덱스(값이 변경 될 인덱스)가 포함되지 않을 경우7
            if (index < start || end < index) {
                // 아무것도 안함
                return;
            }else {
                // 노드가 가지는 값의 구간에 배열의 인덱스(값이 변경 될 인덱스)가 포함되는 경우
                // 노드의 값 + 차이값(변경할 값-기존값)
                tree[node] = tree[node] + diff;

                // 노드가 리프노드가 아닌 경우
                if (start != end) {
                    // 리프노드까지 계속 자식노드를 탐색
                    update(node*2, start, (start+end)/2, index, diff) ;
                    update(node*2+1, (start+end)/2+1, end, index, diff) ;
                }
            }
        }

        // 배열의 특정 인데스의 값이 변경 될 경우 세그먼트 트리의 노드 값 변경(노드 값을 직접 변경)
        long update2(int node, int start, int end, int index, long changeValue) {
            // 노드가 가지는 값의 구간에 배열의 인덱스(값이 변경 될 인덱스)가 포함되지 않을 경우
            if (index < start || end < index) {
                // 트리의 노드 값 리턴
                return tree[node];
            } else if (start == index && end == index) {
                // 노드가 가지는 값의 구간과 배열의 인덱스(값이 변경 될 인덱스)값이 같은 경우
                // 노드의 값을 변경 될 값으로 변경
                return tree[node] = changeValue;
            } else {
                // 노드가 가지는 값의 구간에 배열의 인덱스(값이 변경 될 인덱스)값이 포함되는 경우(같은 경우는 제외)
                // 자식 노드를 탐색 후 값을 더해서 리턴
                return tree[node] = update2(node * 2, start, (start + end) / 2, index, changeValue) +
                        update2(node * 2 + 1, (start + end) / 2 + 1, end, index, changeValue);
            }
        }
    }
}

 

감사합니다.

---