페르마트(Fenwick Tree) 트리와 세그먼트(Segment Tree) 트리

고급 데이터 구조는 복잡한 문제들을 효율적으로 해결하기 위해 필수적입니다. 특히 대규모 데이터 처리나 실시간 쿼리에서 효율성을 극대화할 수 있는 자료구조는 성능을 크게 향상시킬 수 있습니다. 오늘 소개할 고급 데이터 구조로는 페르마트 트리(Fenwick Tree, 또는 Binary Indexed Tree)와 세그먼트 트리(Segment Tree)가 있습니다. 이 두 가지 자료구조는 주로 배열에 대한 구간 합 계산이나 업데이트 작업을 효율적으로 수행하는 데 사용됩니다.

페르마트 트리 (Fenwick Tree)

페르마트 트리는 주로 누적 합 계산 및 부분 합 업데이트를 빠르게 수행하기 위한 자료구조입니다. 이를 통해 $O(\log n)$의 시간 복잡도로 이러한 작업을 수행할 수 있습니다. 이는 큰 데이터셋에서 효과적인 성능을 제공하기 때문에 수많은 알고리즘 문제에 사용됩니다.

주요 개념

페르마트 트리는 각 인덱스에 대해 관련된 부분합을 저장합니다. 이때, 특정 인덱스와 관련된 부분합의 범위는 인덱스의 마지막 비트에 의해 결정됩니다. 이러한 특성을 통해 특정 위치까지의 합이나 특정 위치의 값을 빠르게 구할 수 있습니다.

Java 예제

아래는 페르마트 트리의 기본적인 구현을 Java로 작성한 코드입니다:

class FenwickTree {
    private int[] tree;

    public FenwickTree(int size) {
        tree = new int[size + 1];
    }

    public void update(int index, int value) {
        while (index < tree.length) {
            tree[index] += value;
            index += index & -index;
        }
    }

    public int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= index & -index;
        }
        return sum;
    }

    public int rangeQuery(int left, int right) {
        return query(right) - query(left - 1);
    }

    public static void main(String[] args) {
        FenwickTree fenwickTree = new FenwickTree(10);
        fenwickTree.update(3, 5);
        fenwickTree.update(5, 2);
        fenwickTree.update(7, 3);

        System.out.println("Sum of elements from 1 to 5: " + fenwickTree.query(5));
        System.out.println("Sum of elements from 3 to 7: " + fenwickTree.rangeQuery(3, 7));
    }
}

C 예제

C 언어로도 동일한 기능을 구현할 수 있습니다. 아래는 간단한 페르마트 트리의 구현입니다:

#include <stdio.h>
#define MAX 1000

int tree[MAX + 1];

void update(int n, int index, int value) {
    while (index <= n) {
        tree[index] += value;
        index += index & -index;
    }
}

int query(int index) {
    int sum = 0;
    while (index > 0) {
        sum += tree[index];
        index -= index & -index;
    }
    return sum;
}

int rangeQuery(int left, int right) {
    return query(right) - query(left - 1);
}

int main() {
    int n = 10;
    update(n, 3, 5);
    update(n, 5, 2);
    update(n, 7, 3);

    printf("Sum of elements from 1 to 5: %d\n", query(5));
    printf("Sum of elements from 3 to 7: %d\n", rangeQuery(3, 7));
    return 0;
}

세그먼트 트리 (Segment Tree)

세그먼트 트리는 구간 질의(range query)와 구간 업데이트(range update)를 효율적으로 처리하기 위해 사용되는 자료구조입니다. 세그먼트 트리는 트리 형태로 배열을 표현하여 각 노드가 특정 구간의 정보를 저장하도록 합니다. 이를 통해 구간 합, 최소값, 최대값 등 다양한 질의를 빠르게 수행할 수 있습니다.

주요 개념

세그먼트 트리는 일반적으로 배열의 길이를 $2^k$로 맞추기 위해 여유 공간을 추가합니다. 각 노드는 구간의 합, 최댓값 또는 최솟값과 같은 정보를 저장하며, 이를 통해 $O(\log n)$ 시간 내에 쿼리 및 업데이트가 가능합니다.

Java 예제

아래는 세그먼트 트리의 기본 구현을 Java로 작성한 코드입니다:

class SegmentTree {
    private int[] tree;
    private int n;

    public SegmentTree(int[] data) {
        n = data.length;
        tree = new int[2 * n];
        buildTree(data);
    }

    private void buildTree(int[] data) {
        for (int i = 0; i < n; i++) {
            tree[n + i] = data[i];
        }
        for (int i = n - 1; i > 0; i--) {
            tree[i] = tree[2 * i] + tree[2 * i + 1];
        }
    }

    public void update(int index, int value) {
        index += n;
        tree[index] = value;
        while (index > 1) {
            index /= 2;
            tree[index] = tree[2 * index] + tree[2 * index + 1];
        }
    }

    public int query(int left, int right) {
        left += n;
        right += n;
        int sum = 0;
        while (left <= right) {
            if ((left % 2) == 1) sum += tree[left++];
            if ((right % 2) == 0) sum += tree[right--];
            left /= 2;
            right /= 2;
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] data = {1, 3, 5, 7, 9, 11};
        SegmentTree segmentTree = new SegmentTree(data);

        System.out.println("Sum of elements from 1 to 3: " + segmentTree.query(1, 3));
        segmentTree.update(1, 10);
        System.out.println("Sum of elements from 1 to 3 after update: " + segmentTree.query(1, 3));
    }
}

C 예제

아래는 C 언어로 작성한 세그먼트 트리의 구현입니다:

#include <stdio.h>
#define MAX 1000

int tree[2 * MAX];
int n;

void buildTree(int data[], int size) {
    n = size;
    for (int i = 0; i < n; i++) {
        tree[n + i] = data[i];
    }
    for (int i = n - 1; i > 0; --i) {
        tree[i] = tree[2 * i] + tree[2 * i + 1];
    }
}

void update(int index, int value) {
    index += n;
    tree[index] = value;
    while (index > 1) {
        index /= 2;
        tree[index] = tree[2 * index] + tree[2 * index + 1];
    }
}

int query(int left, int right) {
    left += n;
    right += n;
    int sum = 0;
    while (left <= right) {
        if (left % 2 == 1) sum += tree[left++];
        if (right % 2 == 0) sum += tree[right--];
        left /= 2;
        right /= 2;
    }
    return sum;
}

int main() {
    int data[] = {1, 3, 5, 7, 9, 11};
    int size = sizeof(data) / sizeof(data[0]);
    buildTree(data, size);

    printf("Sum of elements from 1 to 3: %d\n", query(1, 3));
    update(1, 10);
    printf("Sum of elements from 1 to 3 after update: %d\n", query(1, 3));
    return 0;
}

결론

페르마트 트리와 세그먼트 트리는 모두 효율적인 구간 질의와 업데이트를 위해 설계된 자료구조입니다. 페르마트 트리는 구현이 간단하고 메모리 사용이 적다는 장점이 있지만, 세그먼트 트리는 구간의 다양한 연산을 처리하는 데 더 유연한 장점이 있습니다. 문제의 성격에 맞는 자료구조를 선택하는 것이 중요하며, 이러한 고급 자료구조를 이해하고 사용할 수 있다면 더욱 복잡한 문제를 효과적으로 해결할 수 있을 것입니다.