백준/2042번/구간 합 구하기/골드1

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

문제 설명

Site: Baekjoon
Number: 2042
Category: Segment Tree
Rank: Gold 1

여러 개의 숫자가 주어 졌을 때, a,b,c가 입력됐을 때 a가 1인 경우 b번째 숫자를 c로 바꾸고, 2가 입력된 경우 b부터 c까지의 구간 합을 출력하는 문제입니다.

문제 풀이

입력을 받을 때 마다 구간 합을 구한다면 그 때 마다 c-b만큼의 시간이 걸려 시간초과가 발생합니다. 이는 세그먼트 트리를 활용하여 시간 소모를 줄여야 해결할 수 있습니다.

세그먼트 트리: https://grujam.github.io/A&D/SegmentTree/

#include <iostream>

using namespace std;

long long numbers[1000001];
long long sum[2097153];

int N, M, K;

void Sum(int idx, int start, int end)
{
    if(start == end)
    {
        sum[idx] = numbers[start];
        return;
    }

    int mid = (end + start) / 2;

    Sum(idx * 2, start, mid);
    Sum(idx * 2 + 1, mid+1, end);

    sum[idx] = sum[idx * 2] + sum[idx * 2 + 1];
}

void FindSum(int idx, int start, int end, int left, int right, long long& ans)
{
    if (end < left || start > right)
        return;

    if(left <= start && right >= end)
    {
        ans += sum[idx];
        return;
    }

    int mid = (start + end) / 2;

    FindSum(idx * 2, start, mid, left, right, ans);
    FindSum(idx * 2 + 1, mid+1, end, left, right, ans);
}

void FindIdx(const int& num, int idx, int start, int end, int& ret)
{
    if (start > num || end < num)
        return;

    if (start == end && start == num)
    {
        ret = idx;
        return;
    }

    int mid = (start + end) / 2;

    FindIdx(num, idx * 2, start, mid, ret);
    FindIdx(num, idx * 2 + 1, mid+1, end, ret);
}

void Change(int idx, long long num)
{
    long long delta = num - numbers[idx];
    numbers[idx] = num;
    int treeidx = 0;
    FindIdx(idx, 1, 1, N, treeidx);

    do
    {
        sum[treeidx] += delta;
        treeidx /= 2;
    } while (treeidx > 0);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> N >> M >> K;

    for (int i = 1; i < N+1; i++)
        cin >> numbers[i];

    Sum(1, 1, N);

    for(int i = 0; i < M+K; i++)
    {
        long long a, b, c;
        cin >> a >> b >> c;

        if(a == 1)
        {
            Change(b, c);
        }
        else
        {
            long long ans = 0;
            FindSum(1, 1, N, b, c, ans);
            cout << ans << '\n';
        }
    }


    return 0;
}