세그먼트 트리2

류한선·2025년 6월 27일

실기연습-2

목록 보기
48/95

좋아! 이번엔 **동적 계획법이랑 함께 자주 나오는 자료구조인 세그먼트 트리(Segment Tree)**를 아주 간단한 예제와 함께 보여줄게.

🔧 문제 설명 (초간단 세그먼트 트리 버전)

정수 배열이 주어진다.
이 배열에서 구간 합을 구하는 프로그램을 세그먼트 트리로 구현해보자.

📌 입력 예시 (초간단)

배열: [1, 2, 3, 4]
질문: 1번 인덱스부터 2번 인덱스까지의 합은?

👉 정답: 2 + 3 = 5

✅ 전체 코드 (Java)

public class Main {
    static int[] arr = {1, 2, 3, 4};  // 원본 배열
    static int[] tree = new int[16]; // 세그먼트 트리 배열 (충분히 크게)

    public static void main(String[] args) {
        int n = arr.length;
        build(1, 0, n - 1); // 세그먼트 트리 생성
        int left = 1, right = 2; // 구간 [1, 2]의 합을 구하자
        System.out.println(query(1, 0, n - 1, left, right)); // 정답 출력
    }

    static void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(2 * node, start, mid);
            build(2 * node + 1, mid + 1, end);
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }

    static int query(int node, int start, int end, int left, int right) {
        if (right < start || end < left) {
            return 0; // 겹치지 않음
        }
        if (left <= start && end <= right) {
            return tree[node]; // 완전히 포함됨
        }
        int mid = (start + end) / 2;
        int l = query(2 * node, start, mid, left, right);
        int r = query(2 * node + 1, mid + 1, end, left, right);
        return l + r;
    }
}

🧠 한 줄씩 완전 디버깅 해설

static int[] arr = {1, 2, 3, 4};

  • 우리가 다루는 실제 데이터야.
  • 인덱스 기준: arr[0] = 1, arr[1] = 2, arr[2] = 3, arr[3] = 4

static int[] tree = new int[16];

  • 세그먼트 트리는 완전 이진 트리니까, 넉넉하게 4 * n크기만큼 잡음.
  • 여기선 n = 4니까 4 * 4 = 16칸.

int n = arr.length;

  • n = 4

build(1, 0, n - 1);

  • 세그먼트 트리를 만들기 시작
  • node = 1 → 트리의 루트
  • start = 0, end = 3 → 전체 구간

▶️ build() 함수 동작 흐름 (상황 예시)

트리 구조 그림:

           [1]
         /     \
      [2]       [3]
     /  \       /  \
   [4] [5]    [6]  [7]
   0   1      2    3

세그먼트 트리에 저장될 값:

tree[4] = arr[0] = 1
tree[5] = arr[1] = 2
tree[2] = tree[4] + tree[5] = 3

tree[6] = arr[2] = 3
tree[7] = arr[3] = 4
tree[3] = tree[6] + tree[7] = 7

tree[1] = tree[2] + tree[3] = 10

✅ 이제 질의(query)

query(1, 0, 3, 1, 2);
  • 노드 1이 전체 [0,3]이니까 절반 나눔

  1. node 1 → 범위 걸침 → 왼쪽, 오른쪽 자식 탐색

  2. 왼쪽: node 2 = [0,1]

    • 겹침 → 다시 왼쪽 node 4 = [0] → 안 겹침 → 0
    • 오른쪽 node 5 = [1] → 포함 → return tree[5] = 2

  3. 오른쪽: node 3 = [2,3]

    • 왼쪽 node 6 = [2] → 포함 → return 3
    • 오른쪽 node 7 = [3] → 안 겹침 → 0

결과: 2 + 3 = 5

✅ 출력 결과

5

📦 요약

항목내용
세그먼트트리 사용 이유구간합을 빠르게 구하려고
build()트리 만들기 (재귀적으로)
query()주어진 범위의 합 구하기
입력 예시[1, 2, 3, 4], 쿼리 [1, 2]
출력5

좋아! 너가 지정한 이 build() 함수는 세그먼트 트리를 만드는 핵심 부분이야.
그 안에서 재귀 호출을 통해 트리를 완성시키는 구조인데,
초보자가 이해하려면 진짜 "디버깅 수준으로 천천히" 해설해줘야 해.

🔍 먼저 전체 역할부터 정리

static void build(int node, int start, int end)

💡 이 함수는:

  • arr[start ~ end] 구간에 대해
  • 트리의 node번째 위치에
  • 그 구간의 합을 저장해주는 역할을 해

⚙️ 매개변수 설명

파라미터뜻
node트리의 인덱스 번호 (루트는 1번부터 시작)
start배열에서 현재 노드가 담당하는 구간의 시작 인덱스
end배열에서 현재 노드가 담당하는 구간의 끝 인덱스

🧠 예제 배열: arr = {1, 2, 3, 4}

우리가 만드는 트리는 다음과 같은 구조로 만들어짐:

                 node 1 : [0~3]
               /                \
        node 2:[0~1]           node 3:[2~3]
        /         \            /         \
 node 4:[0]  node5:[1]   node6:[2]  node7:[3]

✅ 이제 한 줄씩 해체 + 예제 기반 해설 시작

if (start == end)

🔎 이 줄의 역할:

  • "이 노드는 **리프노드(leaf node)**인가?" 확인
  • 리프노드는 arr의 하나의 원소만 담당하는 노드야.
    예: arr[0], arr[1]처럼 하나만 담당하는 구간

🌱 예시:

처음엔 build(1, 0, 3)부터 시작
→ 이후 쪼개지며 build(4, 0, 0)이 호출됨
→ 이때 start == end == 0이므로 리프노드 도달!

tree[node] = arr[start];

📌 역할:

  • 배열의 값을 트리에 그대로 복사

🔄 예시:

build(4, 0, 0); // arr[0] = 1
→ tree[4] = arr[0] = 1;
트리 인덱스값
tree[4]1

else {

✅ start != end인 경우

→ 이 노드는 하나 이상의 원소를 포함하므로,
→ 왼쪽 자식/오른쪽 자식으로 쪼개서 재귀 호출을 해야 돼

int mid = (start + end) / 2;

📌 역할:

  • 현재 구간을 절반으로 나누기 위한 중간점 계산

🎯 예시:

build(1, 0, 3); → mid = (0 + 3) / 2 = 1
→ 이제 구간 [0,1], [2,3]로 나눌 수 있음

build(2 * node, start, mid);

🛠️ 역할:

  • 왼쪽 자식 노드 재귀 호출
  • 2 * node는 현재 노드의 왼쪽 자식 번호

🎯 예시:

build(1, 0, 3); → 왼쪽 자식: build(2, 0, 1);

→ 이 호출도 다시 쪼개져서:

  • build(4, 0, 0) → tree[4] = arr[0] = 1
  • build(5, 1, 1) → tree[5] = arr[1] = 2

build(2 * node + 1, mid + 1, end);

🛠️ 역할:

  • 오른쪽 자식 노드 재귀 호출
  • 2 * node + 1은 현재 노드의 오른쪽 자식 번호

🎯 예시:

build(1, 0, 3); → 오른쪽 자식: build(3, 2, 3);
→ 그 안에서 build(6,2,2), build(7,3,3)
→ 각각 tree[6] = arr[2] = 3, tree[7] = arr[3] = 4

tree[node] = tree[2 * node] + tree[2 * node + 1];

📌 핵심!!

  • 이 줄이 세그먼트 트리의 핵심
  • 자식 노드들이 계산된 후, 그 값들의 합을 부모에 저장

🧮 디버깅 흐름 예시

  1. tree[4] = 1, tree[5] = 2 → tree[2] = 1 + 2 = 3
  2. tree[6] = 3, tree[7] = 4 → tree[3] = 3 + 4 = 7
  3. 최종 루트: tree[1] = 3 + 7 = 10

📊 전체 디버깅 트리 상태

트리 노드의미값
tree[1]전체 [0~3]10
tree[2][0~1]3
tree[3][2~3]7
tree[4][0]1
tree[5][1]2
tree[6][2]3
tree[7][3]4

🔁 전체 흐름 요약

  1. start == end면 leaf node → 그대로 복사
  2. 아니면 mid 계산해서 왼쪽/오른쪽으로 나눔
  3. 왼쪽/오른쪽 자식들 다 처리한 다음 → 합쳐서 tree[node]에 저장

💬 질문 요약

🔸 이 줄들이 왜 이 위치에 있어야 하나요?

  • 재귀 호출이 **하향식(Top-down)**으로 내려가며,
  • leaf에 도달하고 나서야 부모 노드가 계산 가능하니까,
  • **반드시 자식들을 먼저 처리한 다음, 합산 코드(tree[node] = ...)**가 나와야 해.

좋아! 이제 build()로 세그먼트 트리를 만들었으니,
이제는 그 트리를 이용해서 특정 구간의 합을 빠르게 구하는 query() 함수도 디버깅 수준으로 한 줄 한 줄 완벽하게 해설해줄게.

🔍 먼저 함수 전체 보기

static int query(int node, int start, int end, int left, int right) {
    if (right < start || end < left) {
        return 0;
    }
    if (left <= start && end <= right) {
        return tree[node];
    }
    int mid = (start + end) / 2;
    int l = query(2 * node, start, mid, left, right);
    int r = query(2 * node + 1, mid + 1, end, left, right);
    return l + r;
}

📌 이 함수의 역할

세그먼트 트리를 이용해서 arr[left] ~ arr[right] 구간의 합을 구하는 함수
O(log n) 시간에 구간합을 찾는 게 목표야

🔢 예제 기반 설명

예제:

arr = {1, 2, 3, 4}
query(1, 0, 3, 1, 2) // arr[1] + arr[2] = 2 + 3 = 5

📘 파라미터 설명

매개변수설명
node현재 트리 노드 번호 (루트는 1)
start이 노드가 담당하는 배열의 시작 인덱스
end이 노드가 담당하는 배열의 끝 인덱스
left구하고 싶은 구간의 시작 인덱스
right구하고 싶은 구간의 끝 인덱스

🎯 한 줄씩 자세히 해설

if (right < start || end < left) { return 0; }

✔️ 역할:

  • 현재 노드가 담당하는 구간이 [start, end]
  • 우리가 구하고 싶은 구간은 [left, right]
  • 두 구간이 전혀 겹치지 않는 경우,
    → 이 노드는 아무 기여도 없음 → 0 반환

🔍 예시:

  • 현재 노드 범위: [2,3], 찾고 싶은 범위: [0,1] → 겹침 없음 → 0

if (left <= start && end <= right) { return tree[node]; }

✔️ 역할:

  • 현재 노드가 담당하는 구간이 [start ~ end]
  • 우리가 구하고 싶은 구간 [left ~ right]에 완전히 포함된 경우
  • → 그냥 이 노드의 값을 바로 사용하면 됨

🔍 예시:

  • 현재 노드 범위 [1,1], 구간 [1,2] → 포함됨 → tree[5] = 2 반환

int mid = (start + end) / 2;

✔️ 역할:

  • 현재 구간을 둘로 나누기 위한 중간값 계산
  • 자식 노드로 분할하기 위해 필요

int l = query(2 * node, start, mid, left, right);

✔️ 역할:

  • 왼쪽 자식 노드 탐색
  • 범위는 [start, mid]
  • 왼쪽 노드 번호는 2 * node

int r = query(2 * node + 1, mid + 1, end, left, right);

✔️ 역할:

  • 오른쪽 자식 노드 탐색
  • 범위는 [mid+1, end]
  • 오른쪽 노드 번호는 2 * node + 1

return l + r;

✔️ 역할:

  • 왼쪽, 오른쪽 자식 노드에서 가져온 값을 합쳐서 반환

🧪 디버깅 예제: query(1, 0, 3, 1, 2)

트리 구조 요약:

node구간값
1[0~3]10
2[0~1]3
3[2~3]7
4[0]1
5[1]2
6[2]3
7[3]4

호출 과정 추적 (재귀 호출 트리)

query(1, 0, 3, 1, 2)
├─ query(2, 0, 1, 1, 2)
│  ├─ query(4, 0, 0, 1, 2) → 겹치지 않음 → 0
│  ├─ query(5, 1, 1, 1, 2) → 완전 포함 → tree[5] = 2
│  └─ 합계: 0 + 2 = 2
├─ query(3, 2, 3, 1, 2)
│  ├─ query(6, 2, 2, 1, 2) → 완전 포함 → tree[6] = 3
│  ├─ query(7, 3, 3, 1, 2) → 겹치지 않음 → 0
│  └─ 합계: 3 + 0 = 3
└─ 최종 반환: 2 + 3 = **5**

📌 최종 출력

System.out.println(query(1, 0, 3, 1, 2)); // 출력: 5

🧠 요약

조건행동
[left ~ right]와 전혀 겹치지 않음0 반환
[start ~ end]가 완전히 포함됨tree[node] 바로 반환
일부만 겹침왼쪽/오른쪽 나눠서 합쳐 계산
profile
류한선
good
이전 포스트

구조체

다음 포스트

전체적으로 (주의)

0개의 댓글