[BOJ 11658]

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

solution with segment tree

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

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

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

solution with fenwick tree

펜윅 트리는 위 세그먼트 트리 구현에 비해서 굉장히 쉽다. 2중 for문 외에는 기존의 내용과 변함이 거의 없다.
다만 uplast_modified_at()에서는 기존 값에 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);
    uplast_modified_at(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를, uplast_modified_at는 i~n를 계산한다.
q==0의 경우 val로 교체를 해줘야 하기 때문에 원래값(origin)을 sum으로 구한 후 val에 빼서 diff를 만들고 업데이트 한다.
윗 줄을 이해했다면 합 구하는 부분도 이해할 것이다.