[C#] 세그먼트 트리

코딩을 할 때 시간을 단축하기 위해 메소드를 호출해서 사용하듯이 비슷한 문제를 풀 때마다 같은 알고리즘을 짜는 건 시간낭비이다. 따라서 알고리즘 도장을 파서 적재적소에 활용하고자 한다.

 

세그먼트 트리는 단말 노드에 값들이 저장되고 그 부모노드엔 단말 노드의 값들을 조합한 결과가 저장되는 트리이다. 예를 들어 노드의 합을 저장하는 세그먼트 트리라면, 단말 노드의 일부가 1 / 2 || 3 / 4라면 부모 노드엔 3 / 7이 저장되고 그 부모 노드엔 10이 저장된다. 그리고 뿌리 노드엔 모든 단말 노드의 합이 저장된다. 따라서 어떤 데이터들이 주어질 때, 세그먼트 트리를 만들면 데이터의 특정 구간의 연산(합, 곱, 최대, 최소 등)이 가능하다.

 

노드의 합 세그먼트 트리:  update는 해당 값을 완전히 바꾸는게 아닌 증감 수치를 입력하는 것에 유의(예시에선 원래값에 100이 더해짐)

 

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args) //실행 예
    {
        long[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        long[] leaf = new long[arr.Length * 4];
        TreeSum tree = new TreeSum(arr, leaf);
        tree.init_sum(0, arr.Length - 1, 1);
        Console.WriteLine(tree.sum(0, arr.Length - 1, 1, 0, 10));
        tree.update(0, arr.Length - 1, 1, 5, 100);
        Console.WriteLine(tree.sum(0, arr.Length - 1, 1, 0, 10));
    }
}
class TreeSum   //노드의 합 세그먼트 트리
{
    long[] arr;
    long[] tree;
    public TreeSum(long[] arr, long[] tree)
    {
        this.arr = arr;
        this.tree = tree;
    }
    //트리 만들기) start: 시작 인덱스 end: 마지막 인덱스 node: 트리의 시작 (1)
    public long init_sum(int start, int end, int node)
    {
        if (start == end)
        {
            tree[node] = arr[start];
            return tree[node];
        }
        int mid = (start + end) / 2;
        tree[node] = init_sum(start, mid, node * 2) + init_sum(mid + 1, end, node * 2 + 1);
        return tree[node];
    }
    //합 구하기) left, right:범위
    public long sum(int start, int end, int node, int left, int right)
    {
        if (left > end || right < start)
            return 0; //0을 더함=변화없음
        if (left <= start && right >= end)
            return tree[node];
        int mid = (start + end) / 2;
        return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
    }
    //값 수정하기) index: 변경할 인덱스 dif: 변경할 값
    public void update(int start, int end, int node, int index, long dif)
    {
        if (index < start || index > end)
            return;
        tree[node] += dif;
        if (start == end)
            return;
        int mid = (start + end) / 2;
        update(start, mid, node * 2, index, dif);
        update(mid + 1, end, node * 2 + 1, index, dif);
    }
}

 

최솟값 세그먼트 트리

 

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args) //실행 예
    {
        long[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        long[] leaf = new long[arr.Length * 4];
        TreeMin tree = new TreeMin(arr, leaf);
        tree.init_min(0, arr.Length - 1, 1);
        Console.WriteLine(tree.min(0, arr.Length - 1, 1, 0, 10));
    }
}
class TreeMin   //최솟값 세그먼트 트리
{
    long[] arr;
    long[] tree;
    public TreeMin(long[] arr, long[] tree)
    {
        this.arr = arr;
        this.tree = tree;
    }
    //트리 만들기) start: 시작 인덱스 end: 마지막 인덱스 node: 트리의 시작 (1)
    public long init_min(int start, int end, int node)
    {
        if (start == end)
        {
            tree[node] = arr[start];
            return tree[node];
        }
        int mid = (start + end) / 2;
        tree[node] = Math.Min(init_min(start, mid, node * 2), init_min(mid + 1, end, node * 2 + 1));
        return tree[node];
    }
    //최소값 구하기) left, right:범위
    public long min(int start, int end, int node, int left, int right)
    {
        if (left > end || right < start)
            return (int)1e9 + 1;    //모든 데이터보다 큰 값
        if (left <= start && right >= end)
            return tree[node];
        int mid = (start + end) / 2;
        return Math.Min(min(start, mid, node * 2, left, right), min(mid + 1, end, node * 2 + 1, left, right));
    }
    //값 수정하기)tree[node]=하위 두 노드 중 최소값
    public long update(int start, int end, int node, int index, long dif)
    {
        if (index < start || index > end)
            return tree[node];
        if (start == end)
        {
            tree[node] = dif;
            return tree[node];
        }
        int mid = (start + end) / 2;
        return tree[node] = Math.Min(update(start, mid, node * 2, index, dif), update(mid + 1, end, node * 2 + 1, index, dif));
    }
}

 

최댓값 세그먼트 트리

 

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args) //실행 예
    {
 
        long[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        long[] leaf = new long[arr.Length * 4];
        TreeMax tree = new TreeMax(arr, leaf);
        tree.init_max(0, arr.Length - 1, 1);
        Console.WriteLine(tree.max(0, arr.Length - 1, 1, 0, 10));
    }
}
class TreeMax   //최댓값 세그먼트 트리
{
    long[] arr;
    long[] tree;
    public TreeMax(long[] arr, long[] tree)
    {
        this.arr = arr;
        this.tree = tree;
    }
    //트리 만들기) start: 시작 인덱스 end: 마지막 인덱스 node: 트리의 시작 (1)
    public long init_max(int start, int end, int node)
    {
        if (start == end)
        {
            tree[node] = arr[start];
            return tree[node];
        }
        int mid = (start + end) / 2;
        tree[node] = Math.Max(init_max(start, mid, node * 2), init_max(mid + 1, end, node * 2 + 1));
        return tree[node];
    }
    //최댓값 구하기) left, right:범위
    public long max(int start, int end, int node, int left, int right)
    {
        if (left > end || right < start)
            return -(int)1e9 + 1; //모든 데이터보다 작은 값
        if (left <= start && right >= end)
            return tree[node];
        int mid = (start + end) / 2;
        return Math.Max(max(start, mid, node * 2, left, right), max(mid + 1, end, node * 2 + 1, left, right));
    }
    //값 수정하기)
    public long update(int start, int end, int node, int index, long dif)
    {
        if (index < start || index > end)
            return tree[node];
        if (start == end)
        {
            tree[node] = dif;
            return tree[node];
        }
        int mid = (start + end) / 2;
        return tree[node] = Math.Max(update(start, mid, node * 2, index, dif), update(mid + 1, end, node * 2 + 1, index, dif));
    }
}