[알고리즘] 다익스트라, 세그먼트 트리

1. 다익스트라

https://rltn2121.tistory.com/84

백준 1753 [복습 필수]

 

 

2. 세그먼트 트리

세그먼트 트리의 query와 update함수는 3가지 경우로 나눠서 수행한다.

먼저 s, e, l, r을 다음과 같이 정의한다

s~e: 현재 탐색중인 범위의 왼쪽 ~ 오른쪽

l~r: 검색할 범위의 왼쪽 ~ 오른쪽

 

① 현재 범위가 검색할 범위를 완전 벗어났을 경우

② 현재 범위가 검색할 범위를 포함할 경우

③ 현재 범위, 검색할 범위가 걸쳐있는 경우

왼쪽 서브트리 + 오른쪽 서브트리

ll init(ll root, ll s, ll e) {
    if (s == e) return tree[root] = arr[s];
    ll mid = (s + e) / 2;
    return tree[root] = init(root * 2, s, mid) + init(root * 2 + 1, mid + 1, e);
}
 
ll query(ll root, ll s, ll e, ll l, ll r) {
    if (r<s || e<l) return 0;
    if (l<=s && e <= r) return tree[root];
    ll mid = (s + e) / 2;
    return query(root*2, s, mid, l, r) + query(root*2+1, mid+1, e, l, r);
}
 
ll update(ll root, ll s, ll e, ll idx, ll val) {
    if (idx<s || e<idx) return tree[root];
    if (idx== s && idx== e) return tree[root] = val;
    ll mid = (s + e) / 2;
    return tree[root] = update(root * 2, s, mid, idx, val) + update(root * 2 + 1, mid + 1, e, idx, val);
}

 

 

3. 인덱스 트리

update: 리프 노드의 값을 변경하고, 해당 리프노드의 조상 노드들을 갱신한다.

query: 두 개의 포인터 s, e를 사용하여 구간 합을 계산한다. s는 -> 방향, e는 <- 방향으로 이동한다.

s는 홀수일 때, e는 짝수일 때 해당 위치의 값을 더한다.

0123

void init() {
    for (int i = OFFSET-1; i > 0; i--)
        arr[i] = arr[i * 2] + arr[i * 2 + 1];
}
void update(int node, ll num) {
    node = node + OFFSET - 1;
 
    arr[node] = num;
    node /= 2;
    while (node > 0) {
        arr[node] = arr[node * 2] + arr[node * 2 + 1];
        node /= 2;
    }
}
 
ll query(int s, int e) {
    ll ret = 0;
    s = s + OFFSET - 1;
    e = e + OFFSET - 1;
 
    while (s <= e) {
        if (s % 2 == 1) ret += arr[s];
        if (e % 2 == 0) ret += arr[e];
        
        s = (s + 1) / 2;
        e = (e - 1) / 2;
    }
 
    return ret;
}

인덱스 트리, 세그먼트 트리 둘 다 아래와 같은 구조를 가진다.