세그먼트 트리

기업 코딩테스트에 나오지는 않지만, 좀더 심화된 알고리즘 대회나 코딩테스트에서 사용하는 자료구조
point update와 range query에 대해 O(logn)의 시간에 처리하는 자료구조

세그먼트 트리란

point update와 range query에 효율적이라 하였다.
세그먼트 트리를 만들려면 교환법칙이 성립하는 연산이 적용된 구조여야 한다.
교환법칙이 성립하는 연산 구조에 대해서 세그먼트 트리 자료구조가 효율적이다.
- 특정 값을 업데이트를 좀더 빠르게 하고싶을때 효율적
- 범위의 영역을 빠르게 조회하고 싶을때 효율적

교환 법칙이 성립하는 연산 구조는?

이런 구조가 무엇일까? 주어진 값들에 대해 교환을 하여도 계산결과가 바뀌지 않는것이다.
최대값, 최소값, 구간합이 대표적인 구조이다.
- 예의 최대값을 보면 [a,b,c]로 되어있든, [b,c,a]로 되어있든 최대값은 무조건 하나의 동일한 값이 나온다.

왜 효율적일까

만약 배열이 하나 존재한다고 할때, 구간합을 구하는 문제가 나오면 dp나 완전탐색으로 풀려고 할것입니다.
[1,6,4,12]라는 배열이 존재
- DP로는 [1,7,11,23]과 같이 맨 앞에서 누적된 합의 값의 배열을 만들어 메모이제이션을 통해 빠르게 문제가 해결이 됩니다.
- 0~3의 구간은 dp[0]과 dp[3]을 빼는 상수의 계산으로 해결이 된다.
하지만 dp나 완전탐색은 일단 초기에는 배열의 길이가 n일때 O(n)이 걸리고, 조회는 O(1)정도의 속도로 좋아보입니다.
하지만 특정 값이 변경된다면?
- dp 결과를 한번더 계산해야 하므로 O(n)의 시간이 또 걸릴것입니다.
만약 배열의 길이 n의 값이 1억이고 변경하고 조회하는게 1억이라면?
- 1억 * 1억 만큼 계산을 할것이다.
이럴때 세그먼트 트리 자료구조를 활용한다.

세그먼트 트리의 구현 규칙

세그먼트 트리는 이진 트리로 구현
- 이진트리이므로 1차원 배열로 표현 가능

세그먼트 트리 구조 규칙

규칙
- 루트는 모든 구간의 결과를 저장
- 리프노드는 구간의 길이가 1인 결과를 가진다.
배열 길이가 N이면 트리의 노드 개수는 2N-1이 된다.
구현은 힙과 같은 형태이다.
- 부모의 인덱스i가 있다면 i*2는 왼쪽, i*2+1은 오른쪽자식을 가르킴
모든 리프노드의 인덱스는 N~2N이다.

세그먼트 트리 초기 업데이트

주어진 배열(data) 길이는 N이라고 하자.
세그먼트 트리(segtree)는 길이를 2*N으로 생성
세그먼트 트리에는 구간합들이 저장된다
초기 세그먼트 트리는 리프노드 부터 시작해 루트까지 올라가면서 노드를 업데이트 할것이다.
초기 업데이트
- 먼저 리프노드들 부터 입력한다.
  - 리프노드인 segtree[N]~segtree[2N-1]까지 초기 배열을 넣어준다.
  - segtree[N]에는 배열data[0], segtree[N+1]에는 배열data[1]의값,…, segtree[2N-1]에는 배열data[N-1]의값,…,
  - 리프노드는 N~2N-1를 가르키므로 data[i]는 segtree[i+N]이라는 간단한 계산으로 만들어진다.
- N-1부터 1까지 자식노드를 확인해서 업데이트를 진행한다.
  - 부모(segtree[i]) = 왼쪽자식(segtree[i2]) + 오른쪽 자식(segtree[i2+1])
위의 초기 업데이트를 진행하면 세그먼트 트리의 초기 형태는 만들어진다.

void segtreeInit(int N, int[] data){
    //세그먼트 트리 초기화
    int segtree[] = new int[2*N];

    //리프노드 입력
    for(int i=0;i<N;i++){
        segtree[i+N] = data[i];
    }

    //N-1부터 1(루트)까지 업데이트 진행
    for(int i=N-1;i>0;i--){
        //왼쪽자식은 i*2, 오른쪽은 i*2+1
        segtree[i] = segtree[i*2]+segtree[i*2+1];
    }
}

point update

여기서 특정 값을 변경했을때 세그먼트 트리의 변경을 진행
- 해당 값을 포함하는 범위의 노드들을 전부 수정해줘야 한다.
- 리프노드 부터 시작해 영향을 가지는 부모 노드에게 올라가면서 수정한다.
data[i]의 값을 X로 수정
- segtree[i+N]을 X로 수정한다.
  - 위에서 초기 규칙인 리프 노드는 N~2N에 존재한다는 규칙을 기억하자.
  - 그러면 특정 i의 값은 세그먼트 트리의 i+N와 같다.
- (i+N)/2부터 루트(1)까지 올라가면서 노드를 수정한다.
  - (i+N)/2부터인 이유는 i+N의 부모부터 다시 계산하면 되기때문
    - i의 부모는 i/2를 해주면 된다.
  - segtree[i] = segtree[i2]+segtree[i2+1];

void pointUpdate(int i,int x,int N, int[] segtree){
    //i위치의 값을 x로 변경

    //i의값 수정
    segtree[i+N] = x;


    //segtree를 리프노드인 segtree[i+N]의 부모노드부터 시작해 루트까지 갱신 진행
    for(int i=((i+N)/2);i>0;i--){
        //왼쪽자식은 i*2, 오른쪽은 i*2+1
        segtree[i] = segtree[i*2]+segtree[i*2+1];
    }
}

range query

특정 구간 l부터 r까지에 대한 조회를 진행
- 세그트리의 각 노드는 각자 다른 구간을 가지고 있다.
- 원하는 구간을 포함하는 노드들을 찾고 더하면 된다.
특정구간의 가장왼쪽위치를 l, 오른쪽을 r로 하고 진행
- l과 r이 계속 부모로 가다가 교차되는 순간 종료된다.
- l과 r은 부모로 이동하면서 아래같은 규칙을 따른다.
  - l이 왼쪽자식일때(짝수일때)
    - 바로 부모로 이동합니다. l=l/2로 부모로 이동
      - 왜? 오른쪽 형제는 구간상 l보다 큰 위치.
      - l의 위치는 특정 구간의 가장 왼쪽 위치, 그러므로 오른쪽 형제의 값도 포함하는 부모로 이동한다.
  - l이 오른쪽 자식일때(홀수일때)
    - 더이상 올라가지 않고 해당 값을 더하고, 오른쪽 형제에게 이동한다.
      - 왜? l의 위치는 무조건 가장 왼쪽이어야 한다. 그런데 왼쪽 형제의 구간은 l보다 낮은 구간들의 정보를 가진다.
      - 그러므로 굳이 부모노드로 가서 왼쪽형제의 구간을 확인할 필요가 없음
      - 새로운 구간을 찾아서 오른쪽 형재에게 이동한다.
  - r도 위와 같은 규칙으로 진행 (방향은 반대)
    - 하지만 홀수와 짝수의 작동을 반대로 해야한다.
      - r은 가장 오른쪽 위치이므로
    - r이 왼쪽자식(짝수)이면
      - 해당 노드의 값을 더하고 왼쪽 형제에게 이동.
    - r이 오른쪽자식(홀수)이면
      - 부모노드로 이동.

int rangeQuery(int l, int r, int[] segtree){
    int result = 0;

    //왼쪽 l
    l+=n;
    r+=n;
    while(l<=r){
      //왼쪽
      if(l%2==1){//오른쪽 형제인경우
        result += segtree[l];//현재 노드 합
        l++;//오른쪽 형제에게 이동
      }

      //오른쪽
      if(r%2==0){//왼쪽형제인경우
        result += segtree[r];//현재 노드 합
        r--;//왼쪽형제에게 이동
      }

      //부모로 이동
      l/=2;
      r/=2;
    }

    return result;

}