[2] Segment Tree (Lazy Propagation)

Lazy-Segment Tree는 기본 세그먼트 트리에 구간에 대한 업데이트를 적용하는 쿼리에 적합한 자료구조이다. 

기존 Segment Tree는 매 Update 쿼리마다 Tree의 Leaf node까지 가서 업데이트를 적용하지만

구간에 대해 업데이트가 필요한 경우엔, 그걸 일일이 다 바꿔주는 것이 비효율적이다.

해당 구간을 나중에 조회하지 않을 수도 있기 때문이다. 

 

그럼 해당 구간을 언제 업데이트해줘야 하나?

물론 그 구간을 조회하거나 업데이트 해야 할 때 이다. 그때 아니면 굳이 밑으로 내려갈 필요가 없다. 

해당 구간에 업데이트해야 할 값을 배열로 가지고 있고 (segtree와 동일한 배열)

해당 지점을 update 혹은 find로 접근할 때 propagation을 해준다. 

 

Propagation

void propagation(int node, int S, int E)
{
  if (lazy[node] == 0)
    return;

  segtree[node] += (E - S + 1) * lazy[node];

  if (S != E)
  {
    lazy[node * 2] += lazy[node];
    lazy[node * 2 + 1] += lazy[node];
  }

  lazy[node] = 0;
}

 

해당 node에 대해 값을 계산하고 Lazy 값을 자식 노드로 propagate 시켜준다.  

이런 Propagate를 find 와 update 메소드 호출시 해당 node에 대해 실행해준다.

 

find

ll find(int node, int S, int E, int i, int j)
{
  propagation(node, S, E);

  if (j < S || i > E)
    return 0LL;

  if (i <= S && E <= j)
    return segtree[node];

  return find(node * 2, S, (S + E) / 2, i, j) + find(node * 2 + 1, (S + E) / 2 + 1, E, i, j);
}

 

Update

void update(int node, int S, int E, int i, int j, ll x)
{
  propagation(node, S, E);

  if (i > E || j < S)
    return;

  if (i <= S && E <= j)
  {
    lazy[node] += x;
    propagation(node, S, E);
    return;
  }

  update(node * 2, S, (S + E) / 2, i, j, x);
  update(node * 2 + 1, (S + E) / 2 + 1, E, i, j, x);

  segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
}

 

구간 update시 일치하는 구간에 대해 계산해주고, 1회 Propagate 해준다. 

정확히 말하면 update는 해당 구간은 업데이트하고, 자식 구간들에 대해서만 lazy 값을 적용하는 것이다. 

 

알고리즘 고수 친구에게 항상 감사히 많이 배우고 있다.

열심히 해야지~