[트리] 세그먼트(Segment Tree) 트리란? - 비재귀구현

[ 세그먼트 트리의 개념과 필요성 ]

▶세그먼트 트리란

  여러개의 데이터가 연속적으로 존재할 때 특정한 범위의 합, 특정한 범위의 최소값, 특정한 범위의 최대값을 가장 빠르고 간단하게 구할수 있는 자료구조입니다.

  세그먼트 트리는 대부분 완전 이진 트리입니다.

 

▶ 수열과 쿼리

길이 N인 수열 A1, A2, ..... An이 주어진다 다음 쿼리를 처리하시오. L, R이 주어지면 AL + ..... AR 을 출력하시오 X, V가 주어지면 AX를 V로 바꾸시오

 

▶ 세그먼트트리의 구현 방식

	재귀	비재귀
장점	확장성이 뛰어남 (좀 더 복잡한 형태로 구현 가능)	구현이 간단하고 작동이 빠르다
단점	구현이 상대적으로 복잡하다 작동이 느리다	간단한 형태만 구현 가능하다

---

 

▶ 세그먼트트리( 비재귀구현 으로)를 이용해서 문제를 풀어보도록 하겠습니다.

① 「 백준 11659 - 구간 합 구하기4 」

문제 설명 - 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 

             -  N (1 ≤ N ≤ 100,000), 합을 구해야 하는 횟수 M (1 ≤ M ≤ 100,000)

 

▷ 구간 합 구하기4 소스코드 - 비트연산 사용하지 않고

#include <cstdio>
#define MAX_N 100000

int n;
long long t[MAX_N * 2 +1];

void init()
{
    for(int i=n-1 ; i>0 ; i--)
    {
        t[i] = t[i*2] + t[i*2+1];
    }
}

long long query(int l, int r)
{
    long long ans=0;
    l+=n;
    r+=n;
    do
    {
        if(l%2==1) ans+=t[l++];
        if(r%2==1) ans+=t[--r];
        l/=2;
        r/=2;
    }while(l<r);
    return ans;
}

int main()
{
    int m;
    scanf("%d %d",&n,&m);
    for(int i=0 ; i<n ; ++i)
    {
        scanf("%d",&t[n+i+1]);
    }

    init();

    for(int i=0 ; i<m ; i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        long long q=query(a,b+1);
        printf("%lld\n",q);
    }
    return 0;
}

 

▷ 구간 합 구하기4 소스코드 - 비트연산 사용 - 비트연산은 아래 부분 참고하세요

#include <stdio.h> 
#define MAX_N 100000

int n;
long long t[MAX_N * 2 + 1];

void init() {
    for (int i = n - 1; i > 0; i--){
        t[i] = t[i << 1] + t[i << 1 | 1];
    }
}

long long query(int l, int r) {
    long long ans = 0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l & 1) ans += t[l++];
        if (r & 1) ans += t[--r];
    }
    return ans;
}
int main() {
	int m;
	
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &t[n + i + 1]); 
    }
    init();
	 
	for(int i=0;i<m;i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
    	long long q = query(a, b+1); 
    	printf("%lld\n", q);
    }
    
	return 0;
}

 

---

 

● c언어 비트연산자

연산자	설명	연산자	설명
&	비트 AND	|	비트 OR
~	비트 NOT	^	비트 XOR (배타적 OR, Exclusive OR)
<<	비트를 왼쪽으로 시프트	>>	트를 오른쪽으로 시프트
&=	비트 AND 연산 후 할당	|=	비트 OR 연산 후 할당
^=	비트 XOR 연산 후 할당	<<=	비트를 왼쪽으로 시프트한 후 할당
		>>=	비트를 오른쪽으로 시프트한 후 할당

 

● 다음은 자주 사용하는 비트연산자입니다

연산자	설명	연산자	설명
n & 1	n이 짝수면 0 n이 홀수면 1	n << 1	n값이 2배가 됩니다
n >> 1	n값이 1/2이 됩니다.	n ^ 1	n이 짝수면 n+1 n이 홀수면 n-1
n << 1 | 1	n이 짝수면 n+1 n이 홀수면 n

 

---

 

② 「 백준 2042 - 구간 합 구하기 」 

#include <stdio.h> 
#define MAX_N 1000000

int n;
long long t[MAX_N * 2 + 1];

void init() {
    for (int i = n - 1; i > 0; i--){
        t[i] = t[i << 1] + t[i << 1 | 1];
        //n이 짝수면 n+1
		//n이 홀수면 n 
    }
}


long long query(int l, int r) {
    long long ans = 0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l & 1) ans += t[l++];
        if (r & 1) ans += t[--r];
    }
    return ans;
}

void update(int pos, int val) {
    t[pos + n] = val; // update
    for (pos += n; pos > 1; pos >>= 1) {
        t[pos >> 1] = t[pos] + t[pos ^ 1]; 
		//n이 짝수면 n+1
		//n이 홀수면 n-1 
    }
}

int main() {
	int m,k;
	
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &t[n + i + 1]); 
    }
    init();
	 
	for(int i=0;i<m+k;i++)
	{
		int a, b,c;
		scanf("%d %d %d", &a, &b, &c);
		if(a==1)
		{
			update(b, c);
		}
		else
		{
    		long long q = query(b, c+1); 
    		printf("%lld\n", q);
    	}
    }

	return 0;
}