트리/세그먼트 트리

Top-down 세그먼트 트리

4gats 2024. 2. 13. 12:04

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

 

2042번: 구간 합 구하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄

www.acmicpc.net

 

구간 합 구하기를 Top-Down 방식으로 다시 풀어보자.

 

 

 

<소스 코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
 
typedef long long ll;
 
vector<ll> arr;
vector<ll> Segment_Tree;
 
ll Make_Segment(int node, int start, int end)
{
    // 리프 노드
    if (start == end)
        return Segment_Tree[node] = arr[start];
 
    int mid = start + (end - start) / 2;
    // 왼쪽 범위 (node * 2)
    ll left_val = Make_Segment(node * 2, start, mid);
    // 오른쪽 범위 (node * 2 + 1)
    ll right_val = Make_Segment(node * 2 + 1, mid + 1, end);
    Segment_Tree[node] = left_val + right_val;
    return Segment_Tree[node];
}
 
ll query(int node, int start, int end, int left, int right)
{
    // 탐색하는 범위가 쿼리 구간과 겹치지 않는 경우
    if (left > end || right < start)
        return 0;
 
    // 탐색하는 범위가 찾고자 하는 구간 내인 경우
    // Segment_Tree 값을 return 하면 끝
    if (left <= start && end <= right)
        return Segment_Tree[node];
 
 
    // 일부만 걸쳐있는 경우
    int mid = start + (end - start) / 2;
    ll left_val = query(node * 2, start, mid, left, right);
    ll right_val = query(node * 2 + 1, mid + 1, end, left, right);
    return left_val + right_val;
}
 
 
void Update_Segment(int node, int start, int end, int idx, ll diff)
{
    if (idx < start || idx > end)
        return;
 
    Segment_Tree[node] = Segment_Tree[node] + diff;
 
    if (start != end)
    {
        int mid = start + (end - start) / 2;
        Update_Segment(node * 2, start, mid, idx, diff);
        Update_Segment(node * 2 + 1, mid + 1, end, idx, diff);
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n, m, k;
    cin >> n >> m >> k;
    
    arr.resize(n + 1);
    for (int i = 0; i < n; i++)
        cin >> arr[i];
 
    // 세그먼트 트리 깊이
    int Height = (int)ceil(log2(n));
    int Tree_Size = (1 << (Height + 1));  // 2 ^ (높이 + 1)
    Segment_Tree.resize(Tree_Size);
    Make_Segment(1, 0, n - 1);
    
    for (int i = 0; i < m + k; i++)
    {
        int a, b;
        ll c;
        cin >> a >> b >> c;
 
        if (a == 1)
        {
            int idx = b - 1;
            ll value = c;
            ll diff = value - arr[idx];
            arr[idx] = value;
            Update_Segment(1, 0, n - 1, idx, diff);
        }
        else if (a == 2)
        {
            ll ans = query(1, 0, n - 1, b - 1, c - 1);
            cout << ans << '\n';
        }
    }
    return 0;
}
 
 
 
 cs