세그먼트 트리(Segment Tree)

https://www.acmicpc.net/blog/view/9

https://www.crocus.co.kr/648

세그먼트 트리(Segment Tree)

세그먼트 트리의 루트 노드는 0이 아닌 1부터 시작한다.(1, ...)

배열, vector의 인덱스 번호는 1이 아닌 0부터 시작한다.

함수의 인자들 중에서 node를 제외한 모든 것들은

 vector 또는 배열과 관련된 값들(인덱스, 값 자체 등)이라고 생각하면 된다.

초기 세그먼트 트리 설정하기

long long init_segment_tree(int node, int start, int end)
{
    if (start == end) return tree[node] = v[start];
    return tree[node] = init_segment_tree(2 * node, start, (start + end) / 2)
        + init_segment_tree(2 * node + 1, (start + end) / 2 + 1, end);
}

왼쪽 자식 : 2 * node

오른쪽 자식 : (2 * node) + 1

합 구하기

// 합 구하기
long long sum(int node, int start, int end, int left, int right)
{
    // [left, right]와 [start, end]가 겹치지 않는 경우
    if (left > end || right < start) return 0;
 
    // [left, right]가 [start, end]를 완전히 포함하는 경우
    if (left <= start && end <= right) return tree[node];
 
    // [start, end]가 [left, right]를 완전히 포함하는 경우와
    // [left, right]와 [start, end]가 겹쳐져 있는 경우(위의 3개를 제외 나머지 경우)
    return sum(2 * node, start, (start + end) / 2, left, right) 
        + sum(2 * node + 1, (start + end) / 2 + 1, end, left, right);
}

수 변경하기

// 수 변경하기(index번 째 수를 변경)
void update(int node, int start, int end, int index, long long diff)
{
    // [start, end]에 index가 포함되지 않는 경우
    if (index < start || end < index) return;
 
    // [start, end]에 index가 포함되는 경우
    tree[node] += diff; // 직접적인 세그먼트 트리 내에 있는 배열의 수 변경
 
    // 리프 노드가 아닌 경우에는 자식도 변경해줘야 하기 때문에
    // start != end로 리프 노드인지 검사한다.(같으면 리프 노드임)
    if (start != end)
    {
        update(node, start, (start + end) / 2, index, diff);
        update(node, (start + end) / 2 + 1, end, index, diff);
    }
}

BOJ 2042번 구간 합 구하기

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

#include <bits/stdc++.h>
 
using namespace std;
 
int N, M, K;
 
vector<long long> v, tree;
 
// 초기 세그먼트 트리 설정하기
long long init_segment_tree(int node, int start, int end)
{
    if (start == end) return tree[node] = v[start];
 
    return tree[node] = init_segment_tree(2 * node, start, (start + end) / 2)
        + init_segment_tree(2 * node + 1, (start + end) / 2 + 1, end);
}
 
// 합 구하기
long long sum(int node, int start, int end, int left, int right)
{
    // [left, right]와 [start, end]가 겹치지 않는 경우
    if (left > end || right < start) return 0;
 
    // [left, right]가 [start, end]를 완전히 포함하는 경우
    if (left <= start && end <= right) return tree[node];
 
    // [start, end]가 [left, right]를 완전히 포함하는 경우와
    // [left, right]와 [start, end]가 겹쳐져 있는 경우(위의 3개를 제외 나머지 경우)
    return sum(2 * node, start, (start + end) / 2, left, right) 
        + sum(2 * node + 1, (start + end) / 2 + 1, end, left, right);
}
 
// 수 변경하기(index번 째 수를 변경)
void update(int node, int start, int end, int index, long long diff)
{
    // [start, end]에 index가 포함되지 않는 경우
    if (index < start || end < index) return;
 
    // [start, end]에 index가 포함되는 경우
    tree[node] += diff; // 직접적인 세그먼트 트리 내에 있는 배열의 수 변경
 
    // 리프 노드가 아닌 경우에는 자식도 변경해줘야 하기 때문에
    // start != end로 리프 노드인지 검사한다.(같으면 리프 노드임)
    if (start != end)
    {
        update(2 * node, start, (start + end) / 2, index, diff);
        update(2 * node + 1, (start + end) / 2 + 1, end, index, diff);
    }
}
 
int main(void)
{
    int a;
    long long input;
 
    scanf("%d %d %d", &N, &M, &K);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%lld", &input);
        v.push_back(input);
    }
    
    int h = (int)ceil(log2(N));
    int tree_size = 1 << (h + 1); // 세그먼트 트리 크기
 
    tree.assign(tree_size, 0); // 할당
 
    // 0하고 N - 1은 v vector에 대한 인덱스다.
    init_segment_tree(1, 0, N - 1);
 
    for (int i = 0; i < M + K; i++)
    {
        scanf("%d", &a);
 
        // b번 째 수를 c로 변경
        if (a == 1)
        {
            int b;
            long long c;
 
            scanf("%d %lld", &b, &c);
 
            --b; // b는 vector에 대한 인덱스이므로 1 감소.
            
            long long diff = c - v[b];
 
            v[b] = c;
 
            update(1, 0, N - 1, b, diff);
        }
        else if (a == 2) // b번째 수 ~ c번째 수까지의 합
        {
            int b, c;
 
            scanf("%d %d", &b, &c);
 
            --b; --c; // b와 c는 vector에 대한 인덱스이므로 1씩 감소.
 
            // 1은 루트 노드 번호, 0과 N - 1 그리고 b와 c는 v vector에 대한 인덱스 번호
            printf("%lld\n", sum(1, 0, N - 1, b, c));
        }
    }
 
    return 0;
}