[알고리즘 정리] 세그먼트 트리

세그먼트 트리

update 시간 복잡도 : Log(N)

query 시간 복잡도 : Log(N)

c : 현재 노드

l, r : 현재 노드의 값의 범위

s, f : 찾으려는 값의 범위

val : update 되는 값

기본 코드

ll update(ll c, ll l, ll r ,ll f,ll val)
{
    if(!(l<=f&&f<=r))
        return arr[c];
    else if(l==r)
        return arr[c] = val;
    ll mid = (l+r)/2;
    return arr[c] = update(c*2,l,mid,f,val)+update(c*2+1,mid+1,r,f,val);
}
ll  query(ll c, ll l, ll r, ll s, ll f)
{
    if(r<s||f<l)
        return 0;
    else if(s<=l&&r<=f)
        return arr[c];
    ll mid = (l+r)/2;
    return query(c*2,l,mid,s,f)+query(c*2+1,mid+1,r,s,f);
}

기본 예제

https://www.acmicpc.net/problem/2042

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define MAX 1000005
#define INF 987654321
#define MOD 31991
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

ll n,m,k,a,b,c,arr[MAX*4];

ll update(ll c, ll l, ll r ,ll f,ll val)
{
    if(!(l<=f&&f<=r))
        return arr[c];
    else if(l==r)
        return arr[c] = val;
    ll mid = (l+r)/2;
    return arr[c] = update(c*2,l,mid,f,val)+update(c*2+1,mid+1,r,f,val);
}
ll  query(ll c, ll l, ll r, ll s, ll f)
{
    if(r<s||f<l)
        return 0;
    else if(s<=l&&r<=f)
        return arr[c];
    ll mid = (l+r)/2;
    return query(c*2,l,mid,s,f)+query(c*2+1,mid+1,r,s,f);
}

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