17 Aug 2020

[BOJ 11658]

구간 합 구하기 3

문제 바로가기 : https://www.acmicpc.net/problem/11658
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution with segment tree

지금까지 1차원 세그먼트 트리를 다뤘다면 이 문제는 2차원을 다루는 문제다.
하지만 원래 쓰는 함수와 크게 달라질게 없다. 정말 1차원에서 2차원으로 확장만 했다는 느낌이 체감될 정도다.
트리 모양이 있으면 노드 하나마다 값 1개가 들어갔는데 이제는 세그먼트 트리 하나가 들어간다고 생각하면 된다.
세그먼트 트리로 해결할 수 있고 펜윅 트리로 해결할 수 있다. 위 소스는 세그먼트 트리를 이용했다.
(jh202s님의 글을 참고했습니다. 감사합니다.)

조금 많이 달라진 점이 있다면 update() 부분인데, 하나를 수정하면 모든 세그먼트 트리에 업데이트해줘야 해서 그렇다.
기존에 재귀로 해결했던 부분을 while loop에서 처리하도록 했다.
행이 각 세그먼트 트리를, 열이 현재 세그먼트 트리 내부를 다룬다고 보면 되겠다.

그리고! 혼란스러울 수 있는데 나는 행을 y로 열을 x로 두는걸 선호한다. 문제에서는 행이 x고 열이 y다.
함수 내에서는 전자로 작성돼있으니 이 점 혼동하지 않길 바란다. 인자 꼭 주의해서 체크!

solution with fenwick tree

펜윅 트리는 위 세그먼트 트리 구현에 비해서 굉장히 쉽다. 2중 for문 외에는 기존의 내용과 변함이 거의 없다.
다만 update()에서는 기존 값에 diff를 더해주는 구조이기 때문에 쿼리를 다음과 같이 진행해야 한다.

if (q == 0) {
    int x, y; ll val;
    cin >> x >> y >> val;
    ll origin = sum(x, y) - sum(x - 1, y) - sum(x, y - 1) + sum(x - 1, y - 1);
    update(x, y, val-origin);
}
else {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    if (y1 > y2) swap(y1, y2);
    if (x1 > x2) swap(x1, x2);
    ll ans = sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1);
    cout << ans << '\n';
}

펜윅트리는 sum은 1~i를, update는 i~n를 계산한다.
q==0의 경우 val로 교체를 해줘야 하기 때문에 원래값(origin)을 sum으로 구한 후 val에 빼서 diff를 만들고 업데이트 한다.
윗 줄을 이해했다면 합 구하는 부분도 이해할 것이다.

Location

Icheon, KR

Email

iteratively@naver.com

Social

-->