트리 / Lazy Propagation / Persistent Segment Tree / sqrt Decomposition

[WonYong-Jang]

Segment Tree / Index Tree

백준 관련 문제 2042, 10868, 2357 ( 구간 합, 곱, 최대 최소 구할때 )

• 75, 30, 100, 38, 50, 51, 52, 20, 81, 5 나열되어있는 수 들 중 구간의 합 ==> O(N)
• 하지만 중간의 값들이 계속 바뀌고 그때마다 구간의 합을 구한다면??
• 세그먼트 트리는 자료를 구간별로 나누어 트리에 저장하여 연산을 O(logN) 에 할수 있도록
• 포화 이진트리 형태(full binary tree) 형태로 사용
• 값이 N개일때 반드시 트리의 높이가 O(logN)으로 균형 잡혀 있기 때문

트리 시작점

• 리프 노드에 입력값을 모두 넣어야 하므로 루트 인덱스 1 부터 자식 노드로 내려오면서 N보다 커지는 인덱스가 시작 위치로 지정

  s = 1
  while(N > s) s *=2; 
  ==> N이 10일땐 시작인덱스 16   ( 1 , 2 ,4 ,8 , 16 )

• 값이 N일때 트리 구성하기 위한 전체 배열을 N*4 로 구성 !

• N = 9 일 때 포화 이진트리 구성하기 위한 전체 배열은 31개가 나오므로

트리 구성

• 구간합 : 나머지 값들 0 초기화
• 구간 최소값 : 나머지 값들 가장 큰 수로 초기화
• 구간 최대값 : 나머지 값들 가장 작은 수로 초기화

구간 값 구하기

구간 합 구하기

참고 문제

[WonYong-Jang]

추천문제 확인 !

https://m.blog.naver.com/kks227/220791986409

https://lyzqm.blogspot.com/2017/07/segment-tree-3653.html

[WonYong-Jang]

응용문제

6539 히스토그램에서 가장 큰 직사각형

• 분할정복 인덱스 Tree
• 각 트리의 tree 에는 구간의 최소 높이 막대기의 index 저장 !! ( 중요 )
• 시나리오 1) 1~ N 까지의 구간의 최소높이에 대해 넓이를 구함 2) 그 이후 해당 인덱스의 최소높이를 k라 했을 때 1 ~ k-1 과, k+1 ~ N까지의 각각 분할정복 이용하여 높이 값 구함

1280 나무 심기 ( 다시 풀기 )

• 세그먼트 트리 비용에 대한구간합과 갯수에 대한 구간합 이용
• i 나무에 대한 좌표 xi 라 했을 때 -(xi 보다 왼쪽 좌표에 있는 나무 갯수)*xi - (왼쪽 좌표에 있는 합 )
• (오른쪽 좌표에 있는 합 ) - (xi 보다 오른쪽 있는 나무갯수)*xi

12016 라운드 로빈 ( 다시 풀기 )

• 수행해야할 숫자를 오름차순 정렬
• 수행해야할 시간이 적은 시간부터 처리 하는데, i 번째를 처리하기 위해 수행시간 t 라고 한다면 (1~ i 아직 수행 안된 노드의 수의 합)t + ( i+1 ~ N )(t-1) + preSum
• preSum 은 이전 시간들의 누적합

3392 화성지도

[WonYong-Jang]

세그먼트 트리 with Lazy Propagation

• 일반적인 세그먼트 트리

  public static long init(int node, int start, int end)
  {
  int mid = (start + end) / 2;
  if(start == end) return tree[node] = data[start];
  else return tree[node] = init(node*2, start, mid) + init(node*2+1, mid+1, end);
  }
  public static void update(int node, int start, int end, int target, long diff)
  {
  if(start > target || end < target) return;
  tree[node]+= diff;
  if(start == end) return;
  int mid = (start + end) / 2;
  update(node*2, start, mid, target, diff);
  update(node*2+1, mid+1, end, target, diff);
  }
  public static long sum(int node, int start, int end, int i, int j)
  {
  int mid = (start + end) / 2;
  if(i > end || j < start) return 0;
  else if(i <= start && end <= j) return tree[node];
  else return sum(node*2, start, mid, i, j) + sum(node*2+1, mid+1, end, i, j);
  }

게으른 전파(Lazy Propagation)은 노드의 업데이트를 매 번 리프 노드까지 전부 수행하지 않고,

필요할 때에만 함으로써 하나의 자료뿐만 아니라 구간 내의 자료들 전부를 업데이트 하는 연산마저 O(logN)에 수행 가능

게으르게 전파 시키자

• 구간 업데이트 정보를 반영하기 위해 조상노드의 lazy가 자손노드에 필요한 상황이라면 반드시 조상노드를 거쳐야 자손노드에 도달 할수 있기 때문에 조상 노드를 지날 때 마다 아래쪽을 lazy를 전파 시키면 됨

• 이때 한번 아래쪽으로 전파시키고 나면 다음에 또 지나가면서 같은 lazy가 두번 전파되면 안되기 때문에 lazy값을 대표노드의 값으로 반영하고 0으로 만들어 줌

구간합 2

public static long sum(int node, int start, int end, int i, int j)
{
    if(tree[node].lazy != 0 )
    {
        tree[node].num += (end - start + 1)*tree[node].lazy;
        if(start != end)
        {
            tree[node*2].lazy += tree[node].lazy;
            tree[node*2+1].lazy += tree[node].lazy;
        }
        tree[node].lazy = 0;
    }

    if(i > end || j < start) return 0;
    else if(i <= start && end <= j)
    {
        return tree[node].num;
    }
    else
    {
        int mid = (start + end) / 2;
        return sum(node*2, start, mid, i, j) + sum(node*2+1, mid+1, end, i, j);
    }
}
public static void update(int node, int start, int end, int i, int j, long value)
{
    if(tree[node].lazy != 0)
    {
        tree[node].num += (end - start + 1)*tree[node].lazy;
        if(start != end)
        {
            tree[node*2].lazy += tree[node].lazy;
            tree[node*2+1].lazy += tree[node].lazy;
        }
        tree[node].lazy =0;
    }

    if(i > end || j < start) return;
    else if(i <= start && end <= j)
    {
        tree[node].num += ( end - start + 1)*value;
        if(start != end)
        {
            tree[node*2].lazy += value;
            tree[node*2+1].lazy += value;
        }
        return;
    }
    else
    {
        int mid = (start + end) / 2;
        update(node*2, start, mid, i, j, value);
        update(node*2+1, mid+1, end, i, j, value);
        tree[node].num = tree[node*2].num + tree[node*2+1].num;
    }
}

참고 링크 : https://bowbowbow.tistory.com/4

[WonYong-Jang]

Persistent Segment Tree

• 관련 문제 : 백준 11932, 7469

참고 링크 : http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=221411526404&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=true&from=search

[WonYong-Jang]

모스 알고리즘

Sqrt Decomposition 방법 이용

• 기본 아이디어는 연속적인 원소들을 하나의 묶음으로 생각하자는 것

모든 쿼리 Q = (s, e)에 대해, ([s/√N], e) 순으로 오름차순 정렬

구간 합 구하기

링크 : http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=221401154455&parentCategoryNo=&categoryNo=315&viewDate=&isShowPopularPosts=true&from=search