교재 연습문제

• 『코딩 테스트를 위한 자료구조와 알고리즘 with C++』 37~39페이지

다양한 타입의 데이터 여러 개를 인자로 받아 공통 타입으로 변환하는 함수를 만들어 보자.

#include <array>
#include <iostream>
#include <type_traits>

// 임의 개수의 매개변수를 허용하기 위해 가변 템플릿 사용
template<typename ... Args>

// 모든 인자의 공통 타입 결정
// 전달된 인자의 수만큼 common_type 인자를 갖는 array 반환
auto build_array(Args&&... args) -> std::array<typename std::common_type
<Args...>::type, sizeof...(args)>
{
    using commonType = typename std::common_type<Args...>::type;
    return {std::forward<commonType>((Args&&)args)...};
}

int main()
{
    auto data = build_array(1, 0u, 'a', 3.2f, false);

	// 배열의 모든 원소 출력
    for (auto i: data)
        std::cout << i << " ";
    std::cout << std::endl;

	// int, const char*, double 타입 사용 시 공통 타입을 정할 수 없으므로 주석 처리
    // auto data2 = build_array(1, "Packt", 2.0);
}

백준 15646번

다른분 코드를 매우 참고했습니다. 배열을 벡터로 바꿨을 뿐..

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

// Fenwick Tree
class FenwickTree {
private:
    int height, width;
    vector<vector<long long>> tree;

public:
    // Fenwick Tree의 높이와 너비를 초기화하고 트리 구조를 설정
    FenwickTree(int h, int w) : height(h), width(w), tree(h + 1, vector<long long>(w + 1, 0)) {}

    // 주어진 위치 (h, w)에 val 추가
    void update(int h, int w, long long val) {
        for (int i = h; i <= height; i += i & -i)
            for (int j = w; j <= width; j += j & -j)
                tree[i][j] += val;
    }

    // (1, 1)부터 (h, w)까지의 누적 합 반환
    long long query(int h, int w) {
        long long sum = 0;
        for (int i = h; i > 0; i -= i & -i)
            for (int j = w; j > 0; j -= j & -j)
                sum += tree[i][j];
        return sum;
    }
};

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

    int height, width, q;
    cin >> height >> width >> q;
    FenwickTree fenwick(height, width);

    for (int i = 0; i < q; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            // 영역 업데이트 쿼리 처리
            int x1, y1, x2, y2;
            long long d;
            cin >> x1 >> y1 >> x2 >> y2 >> d;
            fenwick.update(x1, y1, d);
            fenwick.update(x2 + 1, y1, -d);
            fenwick.update(x1, y2 + 1, -d);
            fenwick.update(x2 + 1, y2 + 1, d);
        } else if (op == 2) {
            // 누적 합 쿼리 처리
            int x, y;
            cin >> x >> y;
            cout << fenwick.query(x, y) << '\n';
        }
    }

    return 0;
}

• 펜윅트리: 누적된 구간의 합을 구해야 할 때 적합. 세그먼트 트리의 응용. 메모리는 더 적게 사용. (참고: https://www.acmicpc.net/blog/view/21)