백준 2042 구간 합 구하기

진짜 제곧내 문제 이다.

입력받은 N개의 수에서 두 인덱스 사이의 부분합을 구하거나, 특정 인덱스의 수를 변경하는 두 가지의 연산을 하면 된다.

엄청 나이브하게 접근해서 작동만 하는것을 짰을때는 진짜 말그대로 배열에서 하나씩 탐색하며 부분합을 더했고, 변경도 배열에서 직접 변경하도록 했다. 시간초과인걸로 기억한다. 이런 구간 합 문제에서 투 포인터 알고리즘을 사용할 수도 있었다. 하지만 검색을 해보니 세그먼트 트리로 접근해야 한다고 해서 관련된 내용을 찾아보고 작성했다.

---

세그먼트 트리에 대한 내용은  따로 작성한 포스팅이 있다.

세그먼트 트리는 각 노드가 자신이 포함하고 있는 노드들의 합을 저장하는 트리라고 할 수 있다.

 

코드 전에 각 함수의 로직을 간략히 보면,

init()

• leaf node나오기 전까지 자신의 범위를 반으로 쪼개가며 노드 생성
• leaf node -> 범위 start 값 == 범위 end 값, 이 경우 원래 데이터의 값을 가진다.
• 이 외의 node -> start ~ mid, mid + 1 ~ end로 쪼개서 생성한다.

getSum()

• 내 노드 범위 밖에 있는경우 ret 0;
• 내 노드 범위가 검색 범위에 모두 포함될 경우 내 노드 값 리턴;
• 검색 범위가 내 노드 범위에 포함될 경우 -> start ~ mid, mid + 1 ~ end로 쪼개서 검색 들어가기

updateValue()

• 내 노드 범위 밖에 있는 경우 ret 0;
• 내 노드 범위에 해당 수정 인덱스가 포함될 경우 -> 내 노드 값 diff 만큼 더해주기
• 내 노드 밑에 있는 노드들도 수정해주기(start ~ mid, mid + 1 ~ end)

#include <iostream>
#include <cmath>


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

long long getSum(int start, int end, int node, int left, int right, long long tree[]) {
    if (left > end || right < start)
        return 0;
    if (left <= start && end <= right)
        return tree[node];
    int mid = (start + end) / 2;
    return getSum(start, mid, node * 2, left, right, tree) + getSum(mid+1, end, node * 2 + 1, left, right, tree);
}

void updateValue(int start, int end, int node, int index, long long diff, long long tree[]) {
    if (index < start || index > end)
        return;
    tree[node] += diff;
    if (start == end)
        return ;
    int mid = (start + end) / 2;
    updateValue(start, mid, node * 2, index, diff, tree);
    updateValue(mid + 1, end, node * 2 + 1, index, diff, tree);
}

using namespace std;
int main(void) {
	// 구간 합 트리의 인덱스를 제외하고는 모두 인덱스 0부터 시작
    long long N, M, K, NodeCount;
    cin >> N >> M >> K;
    long long numbers[N];
    for (int i = 0; i < N; i++)
        cin >> numbers[i];
    int height = ceil(log2(N));
    int level = 1;
    NodeCount = 1;
    while (level < N)
    {
        level *= 2;
        NodeCount += level;
    }
    long long tree[1<<(height+1)];
    for (int i = 0; i < NodeCount; i++)
        tree[i] = 0;
	// 구간 합 트리 생성
	init(0, N - 1, 1, tree, numbers);
    int mod = 0, sum = 0;
    for (int i = 0; i < M + K; i++){
        long long a, b, c;
        cin >> a >> b >> c;
        if (a == 1){
        // 5% 틀렸습니다 결정적 부분 -> diff를 선언 후, numbers 배열을 업데이트 해준다.
            long long diff = c - numbers[b-1];
            numbers[b-1] = c;
            updateValue(0, N-1, 1, b-1, diff, tree);
        }
        else if (a == 2) {
            cout << getSum(0, N-1, 1, b - 1, c -1, tree) << '\n';
        }
    }
}

---

구현 후 삽질 - 5%에서 계속 틀렸습니다...

잘 짠것 같은데 계속 틀렸다고 떴다. 찬찬히 로직 따라가다 보니, 값을 업데이트 할때 update 만 해주면 되지~ 하고 안일하게 

updateValue(0, N-1, 1, b-1, c-numbers[b-1], tree)

이렇게 작성을 했다.

단순하게 로컬에서 실행했을땐 그냥 한 인덱스의 숫자를 여러번 바꿔보지 않아서 몰랐지만, 해당 경우로 하게 되면 numbers[] 배열이 업데이트가 되지 않아서 같은 인덱스를 여러번 수정 시 수정되지 않은 numbers[] 배열을 참조하게 되어 오답이 나온다...

수정 후 통과...