글 읽기 - 왜 세그먼트로 풀어야 하는지 모르겠습니

salmon16 3년 전 0

전 그냥 세그먼트 트리를 사용하지 않고 바로 간단하게 풀이를 하였는데 이런식으로 하면 왜안되는지

또 세그먼트리를 이용하면 복잡하게 풀이가 진행되는데 이문제의 어떤 부분에서 세그먼트 트리를 이용하여 풀이하기로 마음먹었는지가 궁금합니다. 감사합니다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N,M,K;
    cin >> N >> M >> K;
    vector<long long> number;
    for (int i = 0;i < N;i++) {
        int num;
        cin >> num;
        number.push_back(num);
    }
    for (int i = 0;i < M+K;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        if (a == 1) {
            number.at(b-1) = c;
        }
        else { // a =2
            long long sum = 0;
            for (int i = b-1;i < c;i++) {
                sum += number.at(i);
            }
            cout << sum << endl;
        }
    }
    return 0;
}

djm03178 3년 전 4

이유는 하나입니다. 지금의 풀이가 시간이 너무 오래 걸리기 때문입니다. 또한 세그먼트 트리를 이용하면 시간을 줄일 수 있기 때문입니다.

세그먼트 트리를 사용하면 특정 구간의 합과 원소 하나의 값을 변경시키는 연산을 각각 O(logN) 시간에 할 수 있어, 질문의 코드에서처럼 구간의 합을 구하는 데에 O(N) 시간이 걸리는 것보다 효율적입니다.

salmon16 3년 전 1

답변 감사드립니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 세그먼트로 풀어야 하는지 모르겠습니

salmon16 3년 전 0

djm03178 3년 전 4

salmon16 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말