2042번 구간 합 구하기

Posted Aug 10, 2025

By matin1202

7 min read

2042번 구간 합 구하기

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

풀이:

문제는 N개의 수가 주어졌을 때, 특정 구간의 합을 구하거나 특정 위치의 수를 변경하는 두 가지 연산을 수행하는 것입니다. 이러한 유형의 문제에서는 세그먼트 트리(Segment Tree) 또는 펜윅 트리(Fenwick Tree)와 같은 자료 구조를 사용하여 효율적으로 처리할 수 있습니다. 여기서는 펜윅 트리를 이용한 풀이를 설명합니다.

펜윅 트리(Fenwick Tree) 접근 방식:

펜윅 트리는 배열의 특정 인덱스까지의 누적 합을 효율적으로 계산하고, 배열의 원소 값을 업데이트하는 데 사용되는 자료 구조입니다. 주로 1차원 배열에 대한 구간 합 질의와 단일 원소 업데이트에 강점을 가집니다.

세부 단계:

클래스 정의: FenwickTree 클래스를 정의합니다. 이 클래스는 내부적으로 tree라는 vector<long long>을 사용하여 펜윅 트리의 노드 값을 저장하고, size는 원본 배열의 크기를 나타냅니다.
생성자: FenwickTree(int n) 생성자는 n을 받아 size를 초기화하고, n+1 크기의 tree 벡터를 0으로 초기화합니다. (펜윅 트리는 보통 1-based indexing을 사용하므로 크기를 n+1로 설정합니다.)
updateImple(int idx, long long delta) 함수:
- 이 함수는 idx에 해당하는 원소의 값이 delta만큼 변경되었을 때, 펜윅 트리를 업데이트하는 내부 함수입니다.
- idx부터 시작하여 idx += idx & -idx 연산을 통해 다음 업데이트가 필요한 상위 노드로 이동하면서 tree[idx]에 delta를 더합니다. idx & -idx는 idx의 가장 낮은 비트를 나타냅니다. 이 연산을 통해 효율적으로 트리를 갱신합니다.
update(int idx, long long val) 함수:
- 이 함수는 원본 배열의 idx번째 원소 값을 val로 변경할 때 사용됩니다.
- 먼저 현재 idx 위치의 원본 값을 알아내기 위해 query(idx, idx)를 호출하여 기존 값을 가져옵니다. (여기서 query(idx, idx)는 단일 원소의 값을 반환합니다.)
- 새로운 값 val과 기존 값 사이의 차이(delta = val - query(idx, idx))를 계산하여 updateImple 함수에 전달하여 트리를 업데이트합니다.
query(int idx) 함수:
- 이 함수는 1부터 idx까지의 누적 합을 계산합니다.
- idx부터 시작하여 idx -= idx & -idx 연산을 통해 다음 검색이 필요한 하위 노드로 이동하면서 tree[idx] 값을 sum에 더합니다. 이 연산을 통해 idx까지의 모든 관련 구간 합을 효율적으로 누적합니다.
query(int l, int r) 함수:
- 이 함수는 l부터 r까지의 구간 합을 계산합니다.
- query(r) - query(l-1) 공식을 사용하여 구간 합을 계산합니다. 이는 1부터 r까지의 합에서 1부터 l-1까지의 합을 빼는 방식입니다.
main 함수:
- N, M, K를 입력받습니다. N은 원소의 개수, M은 값 변경 횟수, K는 구간 합 질의 횟수입니다.
- FenwickTree tree(N)을 선언하여 펜윅 트리를 초기화합니다.
- 초기 N개의 값을 입력받아 tree.update(i, t)를 통해 펜윅 트리를 구성합니다.
- M+K번의 연산을 수행합니다. a가 1이면 업데이트 연산(tree.update(b, c)), a가 2이면 구간 합 질의 연산(tree.query(b, c))을 수행하고 결과를 출력합니다.

시간 복잡도:

펜윅 트리 초기화: \(O(N \log N)\) (각 원소를 업데이트하는 데 \(O(\log N)\)이 걸리므로)
update 연산: \(O(\log N)\) (트리의 높이에 비례)
query 연산: \(O(\log N)\) (트리의 높이에 비례)
총 연산 횟수는 \(M+K\)이므로, 최종 시간 복잡도는 \(O(N \log N + (M+K) \log N)\) 입니다.

공간 복잡도:

펜윅 트리 tree 벡터: \(O(N)\)
최종 공간 복잡도는 \(O(N)\) 입니다.

코드

2042.cpp

#include <bits/stdc++.h>
using namespace std;
class FenwickTree{
private:
    vector<long long> tree;
    int size;
    void updateImple(int idx, long long delta){
        while(idx <= size){
            tree[idx] += delta;
            idx += idx & -idx;
        }
    }
public:
    FenwickTree(int n): size(n), tree(n+1) {}
    void update(int idx, long long val){
        long long delta = val - query(idx, idx);
        updateImple(idx, delta);
    }
    long long query(int idx){
        long long sum = 0LL;
        while(idx > 0){
            sum += tree[idx];
            idx -= idx & -idx;
        }
        return sum;
    }
    long long query(int l, int r){
        return query(r) - query(l-1);
    }
};
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, K;
    cin >> N >> M >> K;
    long long t;
    FenwickTree tree(N);
    for(int i = 1;i<N+1;i++){
        cin >> t;
        tree.update(i, t);
    }
    int a, b;
    long long c;
    while(M + K){
        cin >> a >> b >> c;
        if(a == 1){
            M--;
            tree.update(b, c);
        }
        else{
            K--;
            cout << tree.query(b, c) << '\n';
        }
    }
    return 0;
}

Standard Input (stdin):

C++

BaekJoon

This post is licensed under CC BY 4.0 by the author.

풀이:

코드

Trending Tags