Segment Tree with Lazy Propagation의 비재귀 구현

INDEX

  1. Introduction
  2. Lazy Propagation이란?
  3. Point Update Range Query의 비재귀 구현
  4. Range Update Range Query의 비재귀 구현
  5. Segment Tree 구현 코드
  6. 사용 예시
  7. Segment Tree with Lazy Propagation 구현 코드
  8. 사용 예시

؜

؜

1. Introduction

Segment Tree는 구간의 정보를 효율적으로 관리하는 자료구조입니다. Segment Tree를 이용하면 Point Update와 Range Query를 O(logn)에 처리할 수 있고, Lazy Propagation을 이용한다면 Range Update도 O(logn)에 처리할 수 있습니다.

이번 글에서는 Segment Tree와 Lazy Propagation의 원리를 설명하고, 비재귀 구현을 소개합니다. 세그먼트 트리의 비재귀 구현은 재귀 구현과 같은 시간복잡도, 공간복잡도를 갖지만, 공부해볼 만한 몇 가지 이유가 있습니다. 우선 비재귀 구현은 상수가 작아 빠릅니다. 또한 비재귀 구현은 세그먼트 트리의 노드가 연산에서 이용되는 방식을 이해하기 좋습니다.

글을 읽을 때 필요한 사전 지식은 1)Segment Tree의 구조 및 원리, 2)Segment Tree에서의 Lazy Propagation입니다. 이 주제는 백준님이 작성하신 좋은 글(https://www.acmicpc.net/blog/view/9, https://www.acmicpc.net/blog/view/26)이 있으니 참고하시면 좋을 거 같습니다.

؜

؜

2. Lazy Propagation이란?

Lazy Propagation은 서브트리의 노드의 val을 특정 연산을 적용해 업데이트할 때, 루트노드만 업데이트를 해두고, 나머지는 필요할 때마다 하나씩 업데이트를 하며 시간복잡도를 줄이는 테크닉입니다.

Add Update Sum Query 세그먼트 트리를 예시로 Lazy Propagation의 원리를 알아보겠습니다. 편의를 위해 Update에서 사용하는 연산(=Add)은 U, 두 노드의 val을 합칠 때 사용하는 연산(=Sum)은 M이라 하겠습니다. 세그먼트 트리의 노드는 "val := 서브트리의 리프노드의 val을 M 연산으로 합쳐준 값"을 관리합니다.

Update 연산 _ 단일 트리

fig1.png?raw=true

서브트리의 리프노드의 val에 U 연산을 적용하는 Update 연산을 생각해보겠습니다. 연산이 영향을 미치는 노드의 개수는 O(n)개이므로 Naive하게 Update 연산을 구현하면 시간복잡도는 O(n)이 됩니다. 하지만 루트노드만 val을 갱신해주고, 루트노드의 lazy값에 "자신을 제외한 나머지 서브트리에 Update 연산을 적용하라"는 표시를 해두면 시간복잡도를 O(1)로 줄일 수 있습니다. 이 방법을 Lazy Propagation이라 부릅니다.

Lazy Propagation에서 노드 u의 val값을 이용할 땐 항상 u와 u의 모든 조상 노드들에 남아있는 Update 연산이 없어야 합니다. 이유는 u에 적용되었어야 할 Update 연산이 아직 적용되지 않았을 수도 있기 때문입니다.

Query 연산 _ 단일 노드

fig2.jpg?raw=true

노드 u의 val을 구하는 Query 연산을 생각해보겠습니다. u의 val을 구하기 위해선 u의 조상 노드들을 위에서부터 순회하면서 남아있는 Update 연산을 전파해줘야 합니다. Query 연산의 시간복잡도는 O(u의 조상 노드 개수) = O(logn)입니다.

Update 연산 _ [l, r] 구간

fig3.png?raw=true

이번엔 세그먼트 트리의 전체 구조에서 [l, r] 구간의 리프노드의 val에 U 연산을 적용하는 Update 연산을 생각해보겠습니다. 세그먼트 트리의 노드는 1)Update 연산에 영향을 받지 않는 하얀색 노드, 2)서브트리의 모든 리프노드에 Update 연산이 적용되는 파란색 영역의 노드, 3)서브트리의 일부 리프노드에 Update 연산이 적용되는 초록색 노드로 나눌 수 있습니다.

파란색 영역의 노드들은 Lazy Propagation을 이용하면 서브트리의 루트노드(=파란색 노드)만 갱신하면 됩니다. Lazy Propagation에서 val을 갱신할 땐 val이 올바르게 구해져있어야 하니, 우선 파란색 노드의 조상 노드들을 위에서부터 순회하며 Update 연산을 전파해줍니다. 다음엔 파란색 노드에 Lazy Propagation을 적용해줍니다. 파란색 노드의 val값을 모두 갱신한 뒤엔 마지막으로 파란색 노드의 조상 노드들의 val값을 아래에서부터 다시 구해줍니다.

시간복잡도를 분석해보겠습니다. 관리하는 구간의 길이가 같은 파란색 노드는 최대 2개이니 파란색 노드의 개수는 O(logn)개입니다. 파란색 노드의 조상 노드들은 하얀색 노드가 아니니 항상 초록색 노드입니다. 또한 초록색 노드는 하얀색 리프노드와 파란색 영역의 리프노드를 모두 가지기 때문에 항상 l 또는 r의 조상입니다. 따라서 초록색 노드의 개수는 O(logn)개이고, Update 연산의 시간복잡도는 O(logn)입니다.

Query 연산 _ [l, r] 구간

fig3.png?raw=true

마지막으로 [l, r] 구간의 리프노드의 val을 M 연산으로 합친 결과를 구하는 Query 연산을 생각해보겠습니다. Query 연산의 결과는 파란색 노드의 val만 M 연산으로 합쳐주면 구할 수 있습니다. 따라서 우선 초록색 노드들을 순회하며 Update 연산을 전파해줍니다. 다음엔 파란색 노드를 순회하며 val을 M 연산으로 합쳐주면 됩니다. Query 연산의 시간복잡도는 O(logn)입니다.

؜

+)

Add Update Sum Query 이외에도 다양한 연산을 U, M으로 사용해 Segment Tree with Lazy Propagation을 구현할 수 있습니다. 이때 U, M은 다음의 조건을 만족해야 합니다.

M은 결합법칙을 만족

세그먼트 트리는 [l, r] 구간에 M 연산을 적용한 결과를 [l, *], [*, *], ..., [*, r]로 쪼개서 구하기 때문에 M 연산은 결합법칙을 만족해야 합니다. 즉, M(M(a, b), c) = M(a, M(b, c))여야 합니다. 이 성질을 만족하는 M 연산은 sum, min, max, gcd 등이 있습니다.

U는 M과 분배법칙을 만족

Lazy Propagation은 서브트리의 리프노드에 U 연산을 적용하는 걸 루트노드만 갱신한 뒤 lazy값을 기록하는 방식으로 동작합니다. 이를 위해선 루트노드의 val을 이용해 리프노드에 U 연산을 적용한 뒤 M 연산으로 합친 결과를 빠르게 구할 수 있어야 합니다. 따라서 U 연산은 M 연산과 분배법칙을 만족해야 합니다. 즉, U(c, M(a, b)) = M(U(c, a), U(c, b))여야 합니다. 이 성질을 만족하는 (U, M) 연산은 (sum, sum), (sum, min), (gcd, gcd) 등이 있습니다. 사실 (sum, sum) 연산은 3 + (1 + 2) != (3 + 1) + (3 + 2)라 성질을 만족하지 않아서, 연산의 정의를 약간 바꿔서 처리해야 합니다. 자세한 내용은 6. 사용 예시에서 알아보겠습니다.

((min, sum)은 min(2, sum(1, 3)) != sum(min(2, 1), min(2, 3))이라 성질을 만족하지 않으므로 min update sum query는 lazy propagation으로 구현할 수 없습니다)

؜

؜

3. Point Update Range Query의 비재귀 구현

Lazy Propagation의 비재귀 구현에 앞서서 일반적인 세그먼트 트리의 비재귀 구현을 먼저 알아보겠습니다. Point Update는 Naive하게 구현해도 업데이트되는 노드의 개수가 O(logn)개라 Lazy Propagation 없이 구현할 수 있습니다.

Point Update

fig4.png?raw=true

Point Update는 리프노드의 val에 업데이트를 적용한 뒤, 부모로 올라가면서 초록색 노드의 val을 다시 계산합니다.

구현은 노드 i의 부모 노드가 i >> 1(= i / 2)임을 이용합니다.

Range Query

fig5.png?raw=true

Range Query는 파란색 노드를 순회하며 val을 구해주면 됩니다. 모든 파란색 노드는 홀수 노드와 짝수 노드로 나눌 수 있습니다. 홀수 노드는 l에서 시작해서 홀수일 때마다 오른쪽으로 한 칸씩 이동하며 위로 올라가면 순회할 수 있습니다. 짝수 노드는 r에서 시작해서 짝수일 때마다 왼쪽으로 한 칸씩 이동하며 위로 올라가면 순회할 수 있습니다. 따라서 l, r에서 시작해서 적절히 오른쪽, 왼쪽으로 이동하며 위로 올라가면 모든 파란색 노드를 순회할 수 있습니다.

구현은 노드 i의 오른쪽, 왼쪽 노드가 i + 1, i - 1임을 이용합니다.

؜

؜

4. Range Update Range Query의 비재귀 구현

Range Update는 Naive하게 구현하면 업데이트되는 노드의 개수가 O(n)개라 Lazy Propagation이 필요합니다.

Range Update

fig6.png?raw=true

Range Update에서 Lazy Propagation을 이용한다면 실제로 갱신이 되는 노드는 파란색 노드와 초록색 노드입니다. 구현은 우선 초록색 노드를 위에서부터 순회하며 남아있던 lazy를 전파해주고, 파란색 노드에 lazy propagation을 적용한 뒤, 초록색 노드를 아래에서부터 순회하며 val을 다시 계산해주면 됩니다.

구현에서 초록색 노드는 l 또는 r의 조상노드이고, 서브트리의 가장 왼쪽 또는 오른쪽 리프노드가 하얀색이라는 점을 이용해 ((l >> i) << i) != l, (((r + 1) >> i) << i) != r + 1인 l >> i, r >> i로 순회합니다. 파란색 노드는 위의 Range Query에서 순회하던 것처럼 순회하면 됩니다.

Range Query

fig6.png?raw=true

Range Query는 파란색 노드를 순회하며 val을 구해주면 됩니다. Lazy Propagation을 이용한다면 파란색 노드에 적용되었어야 할 업데이트 연산이 아직 적용되지 않았을 수 있습니다. 따라서 구현은 우선 초록색 노드를 위에서부터 순회하며 남아있던 lazy를 전파해주고, 파란색 노드를 순회하며 val을 합쳐주면 됩니다.

구현은 Range Update와 동일하게 초록색, 파란색 노드를 순회하면 됩니다.

؜

؜

5. Segment Tree 구현 코드

// Point Update Range Query를 비재귀로 구현한 코드입니다.

/*
 * Author : jinhan814
 * Date : 2022-04-16
 * Description : Non-recursive implementation of Segment Tree
 */

template<typename NodeType, typename F_Merge>
struct SegTree { // 1-indexed
public:
    using A = NodeType;
    SegTree() : SegTree(0, A()) {}
    explicit SegTree(int n, const A& e) : n(n), lg(Log2(n)), sz(1 << lg), e(e), tree(sz << 1, e) {}
    void Set(int i, const A& val) { tree[--i | sz] = val; }
    void Init() { for (int i = sz - 1; i; i--) tree[i] = M(tree[i << 1], tree[i << 1 | 1]); }
    void Update(int i, const A& val) {
        tree[--i |= sz] = val;
        while (i >>= 1) tree[i] = M(tree[i << 1], tree[i << 1 | 1]);
    }
    A Query(int i) const { return tree[--i | sz]; }
    A Query(int l, int r) const {
        A L = e, R = e;
        for (--l |= sz, --r |= sz; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) L = M(L, tree[l++]);
            if (~r & 1) R = M(tree[r--], R);
        }
        return M(L, R);
    }
private:
    const int n, lg, sz; const A e; vector<A> tree; F_Merge M;
    static int Log2(int n) { int ret = 0; while (n > 1 << ret) ret++; return ret; }
};

Template Parameter

  1. NodeType : node의 자료형.
  2. F_Merge : (NodeType, NodeType)을 매개변수로 받아서 NodeType을 반환하는 Functor. 두 노드를 합치는 연산을 수행.

// F_Merge는 결합법칙을 만족해야 합니다.

Constructor

  1. LazySegTree() : 크기가 0인 세그먼트 트리 생성.
  2. LazySegTree(n, e) : 크기가 n인 세그먼트 트리 생성. F_Merge 연산의 항등원을 매개변수로 받음.

// F_Merge는 항등원(NodeType)이 존재해야 합니다.

Helper Function

  1. Log2(n) : n <= 2^i인 i의 최솟값을 반환.

Member Function

  1. Set(i, val) : i번 리프노드의 값을 val로 설정. Init을 호출하기 전엔 Update, Query 연산을 호출할 수 없음.
  2. Init() : Set으로 모든 리프노드의 값을 설정한 뒤에 O(n)에 트리를 구성.
  3. Update(i, val): i번 리프노드의 값을 val로 갱신.
  4. Query(i) : i번 리프노드의 값을 반환.
  5. Query(l, r): [l, r] 범위의 리프노드의 값을 합친 값을 반환.

// Update, Query 연산은 세그먼트 트리의 리프노드를 Set으로 초기화하고 Init을 실행한 뒤에 사용해야 합니다.

// 모든 인덱스는 [1, n] 범위여야 합니다.

؜

؜

6. 사용 예시

구현 코드를 사용하려면 문제 별로 적절히 NodeType, F_Merge를 구현해야 합니다.

F_Merge

F_Merge는 결합법칙을 만족하고 항등원이 존재해야 합니다. 구간 합 구하기를 예로 들면 F_Merge(a, b)를 a + b를 반환하도록 정의하면 결합법칙을 만족하고, 항등원은 0이 됩니다.

예시 코드

BOJ 2042 : http://boj.kr/3f0f0670d51141c188688a4e108df3eb

BOJ 2357 : http://boj.kr/9e5367182ec5422ab96614104ab3e1aa

BOJ 14428 : http://boj.kr/b6e0d73c5cae4013820b6b57f90a049c

BOJ 10167 : http://boj.kr/07c2013d7626444c83541f24797398a1

؜

؜

7. Segment Tree with Lazy Propagation 구현 코드

// Range Update Range Query를 비재귀로 구현한 코드입니다. 구현은 AtCoder Library의 lazysegtree.hpp를 참고했습니다.

/*
 * Author : jinhan814
 * Date : 2022-04-16
 * Description : Non-recursive implementation of Segment Tree with Lazy Propagation
 */

template<typename NodeType,
         typename LazyType,
         typename F_Merge,
         typename F_Update,
         typename F_Composition>
struct LazySegTree { // 1-indexed
public:
    using A = NodeType;
    using B = LazyType;
    LazySegTree() : LazySegTree(0, A(), B()) {}
    explicit LazySegTree(int n, const A& e, const B& id)
        : n(n), e(e), id(id), lg(Log2(n)), sz(1 << lg), tree(sz << 1, e), lazy(sz, id) {}
    void Set(int i, const A& val) { tree[--i | sz] = val; }
    void Init() { for (int i = sz - 1; i; i--) Pull(i); }
    void Update(int i, const B& f) {
        --i |= sz;
        for (int j = lg; j; j--) Push(i >> j);
        Apply(i, f);
        for (int j = 1; j <= lg; j++) Pull(i >> j);
    }
    void Update(int l, int r, const B& f) {
        --l |= sz, --r |= sz;
        for (int i = lg; i; i--) {
            if (l >> i << i != l) Push(l >> i);
            if (r + 1 >> i << i != r + 1) Push(r >> i);
        }
        for (int L = l, R = r; L <= R; L >>= 1, R >>= 1) {
            if (L & 1) Apply(L++, f);
            if (~R & 1) Apply(R--, f);
        }
        for (int i = 1; i <= lg; i++) {
            if (l >> i << i != l) Pull(l >> i);
            if (r + 1 >> i << i != r + 1) Pull(r >> i);
        }
    }
    A Query(int i) {
        --i |= sz;
        for (int j = lg; j; j--) Push(i >> j);
        return tree[i];
    }
    A Query(int l, int r) {
        A L = e, R = e; --l |= sz, --r |= sz;
        for (int i = lg; i; i--) {
            if (l >> i << i != l) Push(l >> i);
            if (r + 1 >> i << i != r + 1) Push(r >> i);
        }
        for (; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) L = M(L, tree[l++]);
            if (~r & 1) R = M(tree[r--], R);
        }
        return M(L, R);
    }
private:
    const int n, lg, sz; const A e; const B id;
    vector<A> tree; vector<B> lazy;
    F_Merge M; F_Update U; F_Composition C;
    static int Log2(int n) {
        int ret = 0;
        while (n > 1 << ret) ret++;
        return ret;
    }
    void Apply(int i, const B& f) {
        tree[i] = U(f, tree[i]);
        if (i < sz) lazy[i] = C(f, lazy[i]);
    }
    void Push(int i) {
        Apply(i << 1, lazy[i]);
        Apply(i << 1 | 1, lazy[i]);
        lazy[i] = id;
    }
    void Pull(int i) {
        tree[i] = M(tree[i << 1], tree[i << 1 | 1]);
    }
};

struct NodeType {};
constexpr NodeType e;

struct LazyType {};
constexpr LazyType id;

struct F_Merge {
    NodeType operator() (const NodeType& a, const NodeType& b) const {
    }
};

struct F_Update {
    NodeType operator() (const LazyType& a, const NodeType& b) const {
    }
};

struct F_Composition {
    LazyType operator() (const LazyType& a, const LazyType& b) const {
    }
};

Template Parameter

  1. NodeType : node의 자료형.
  2. LazyType : lazy값의 자료형.
  3. F_Merge : (NodeType, NodeType)을 매개변수로 받아서 NodeType을 반환하는 Functor. 두 노드를 합치는 연산을 수행.
  4. F_Update : (LazyType, NodeType)을 매개변수로 받아서 NodeType을 반환하는 Functor. 노드에 lazy값을 적용하는 연산을 수행.
  5. F_Composition : (LazyType, LazyType)을 매개변수로 받아서 LazyType을 반환하는 Functor. lazy값 위에 lazy값을 적용하는 연산을 수행.

// F_Merge는 결합법칙을 만족해야 하고, F_Update는 F_Merge와 분배법칙을 만족해야 합니다.

Constructor

  1. LazySegTree() : 크기가 0인 세그먼트 트리 생성.
  2. LazySegTree(n, e, id) : 크기가 n인 세그먼트 트리 생성. F_Merge 연산의 항등원인 e와 F_Update에서 항등함수 역할을 하는 id를 매개변수로 받음.

// F_Merge는 항등원(NodeType)이 존재해야 하고, F_Update에선 항등함수(LazyType)가 존재해야 합니다.

Helper Function

  1. Log2(n) : n <= 2^i인 i의 최솟값을 반환.
  2. Apply(i, f) : i번 노드에 f 업데이트를 적용하고, i번 노드의 lazy에 "서브트리에 f 업데이트를 적용하라"는 표시를 남김.
  3. Push(i) : i번 노드의 lazy를 i번 노드의 두 자식에 전파하고, lazy를 id로 변경. i번 노드의 두 자식은 lazy[i] 업데이트가 적용된 뒤, "서브트리에 lazy[i]를 적용하라"는 표시가 남음.
  4. Pull(i) : i번 노드의 val을 i번 노드의 두 자식의 val을 합친 값으로 갱신.

Member Function

  1. Set(i, val) : i번 리프노드의 값을 val로 설정. Init을 호출하기 전엔 Update, Query 연산을 호출할 수 없음.
  2. Init() : Set으로 모든 리프노드의 값을 설정한 뒤에 O(n)에 트리를 구성.
  3. Update(i, f): i번 리프노드에 f 업데이트를 적용.
  4. Update(l, r, f) : [l, r] 범위의 리프노드에 f 업데이트를 적용.
  5. Query(i) : i번 리프노드의 값을 반환.
  6. Query(l, r): [l, r] 범위의 리프노드의 값을 합친 값을 반환.

// Update, Query 연산은 세그먼트 트리의 리프노드를 Set으로 초기화하고 Init을 실행한 뒤에 사용해야 합니다.

// 모든 인덱스는 [1, n] 범위여야 합니다.

؜

؜

8. 사용 예시

구현 코드를 사용하려면 문제 별로 적절히 NodeType, LazyType, F_Merge, F_Update, F_Composition을 구현해야 합니다.

F_Merge

F_Merge는 결합법칙을 만족하고 항등원이 존재해야 합니다. 항등원은 존재한다면 그냥 사용하면 되고, 만약 존재하지 않는다면 임의로 항등원을 정의해주면 됩니다(특정 값을 항등원으로 이용하면서 F_Merge에서 a가 항등원이면 항상 b를 반환하고, b가 항등원이면 항상 a를 반환하도록 하면 됩니다). 구간 합 구하기 2를 예로 들면 F_Merge(a, b)를 (a.val + b.val, a.sz + b.sz)로 정의하면 결합법칙을 만족하고, 항등원은 (0, 0)입니다.

F_Update

F_Update는 F_Merge와 교환법칙을 만족하고 항등함수가 존재해야 합니다. 교환법칙에서 실수할 여지가 많으니 예시를 보면서 주의사항을 알아보겠습니다. 구간 합 구하기 2는 F_Merge는 값의 덧셈을 이용하고, F_Update는 구간에 t를 더하는 연산을 구현해야 합니다. 이때, [1, 2] 구간에 3을 더하는 경우는 (1 + 2) + 3 != (1 + 3) + (2 + 3)이므로 교환법칙이 성립하지 않습니다. 이 문제는 NodeType에 (val, sz)를 저장하며 구간의 합과 구간의 길이를 관리하고, F_Update에서 (val, sz) 구간에 t를 더하는 연산을 (val + t * sz, sz)을 반환하도록 하면 해결됩니다. 결합법칙이 성립하는 이유에 대한 설명은 연습으로 남깁니다. 항등함수는 F_Update를 적용해도 NodeType값이 바뀌지 않도록 하는 LazyType이고, 이 정의에서는 t = 0이 항등함수가 됩니다. 만약 항등함수가 존재하지 않는다면 임의로 항등함수를 정의해주면 됩니다.

F_Composition

F_Composition은 lazy값이 있는 노드 위에 새로 LazyType을 덮어씌울 때 사용합니다. 예를 들어 수열과 쿼리 13에선 LazyType(a, b)가 n -> a * n + b 연산으로 정의됩니다. 여기서 F_Composition(L1, L2)는 n에 L2, L1 연산을 차례로 적용시키면 n -> L2.a * n + L2.b -> L1.a * (L2.a * n + L2.b) + L1.b이므로 LazyType(L1.a * L2.a, L1.a * L2.b + L1.b)를 반환합니다. 구현은 함수의 합성을 생각하면서 처리하면 됩니다.

예시 코드

BOJ 10999 : http://boj.kr/686d528dbdce47c18acb56bb50265c71

BOJ 13925 : http://boj.kr/9190ec416c9940f1b988bb92f6315215

BOJ 12844 : http://boj.kr/e64a14e9b7b24e9dbd8d99be460f871e

BOJ 12895 : http://boj.kr/098b1664bae34c1cac9b6f026446f8b1

؜

؜

reference

[1] https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp

[2] https://atcoder.github.io/ac-library/master/document_en/lazysegtree.html

[3] https://codeforces.com/blog/entry/1256


댓글 (2개) 댓글 쓰기


dohoon 2달 전

비재귀 세그는 배열 크기를 $2^k$로 안 잡아도 됩니다!


didwns7347 2달 전

잘읽고갑니다~~