구간 합 구하기 - 2042번 백준

문제

문제 난이도 : 골드 1

문제 분류: 셰그먼트 트리

 

문제 리뷰

• 코드 자체는 알고리즘 코딩 테스트 DO IT 편을 참조하였다.
• 재귀 셰그먼트 참고 해서 구현 했다가, 안되어서 비재귀 셰그먼트 트리로 구현하였는데 이게 더 나은 것 같다는 생각이..
• 재귀 셰그먼트 안되었던게 로직이 이상한게 아니었고, "\n"을 안해줘서 틀렸다고 뜬 거였다..

 

문제 소스 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <memory.h>

using namespace std;
int N,M,K;
static vector<long> Tree;

void Init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    std::cout.tie(NULL);
}
void SetTree(int i) {
    while (i != 1) {
        Tree[i / 2] += Tree[i];
        i--;
    }
}

void Change(int idx, long ToChange) {
    long diff = ToChange - Tree[idx];

    while (idx > 0) {
        Tree[idx] = Tree[idx] + diff;
        idx /= 2;
    }

}

long GetSum(int s, int e) {
    long Sum = 0;
    while (s <= e) {
        if (s % 2 == 1) {
            Sum += Tree[s];
            s++;
        }
        if (e % 2 == 0) {
            Sum += Tree[e];
            e--;
        }
        s /= 2;
        e /= 2;
    }
    return Sum;
}

int main()
{
    Init();
    cin >> N >> M >> K;
    int TreeHeight = 0;
    int Length = N;
    while (Length != 0) {
        Length /= 2;
        TreeHeight++;
    }
    int TreeSize = int(pow(2, TreeHeight + 1));
    int LeafNodeStartIdx = TreeSize / 2 + 1;
    Tree.resize(TreeSize+1);
    for (int i = LeafNodeStartIdx + 1; i <= LeafNodeStartIdx + N; i++) {
        cin >> Tree[i];
    }
    SetTree(TreeSize - 1);
    for (int i = 0; i < M + K; i++) {
        int a, b;
        long c;
        cin >> a >> b >> c;
        if (a == 1) {
            Change(b + LeafNodeStartIdx, c);
        }
        else {
            cout << GetSum(b + LeafNodeStartIdx, c + LeafNodeStartIdx) << "\n";
        }
    }

}