구간 합 구하기

https://www.acmicpc.net/problem/2042

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	86858	20690	10615	24.949%

문제

어떤 N개의 수가 주어져 있다.

그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다.

만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다.

그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다.

M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다.

그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다.

그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데,

a가 1인 경우 b(1 ≤ b ≤ N)번째 수를 c로 바꾸고

a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 합을 구하여 출력하면 된다.

입력으로 주어지는 모든 수는 -2⁶³보다 크거나 같고, 2⁶³-1보다 작거나 같은 정수이다.

출력

첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다.

단, 정답은 -2⁶³보다 크거나 같고, 2⁶³-1보다 작거나 같은 정수이다.

예제 입력 1

5 2 2
1
2
3
4
5
1 3 6
2 2 5
1 5 2
2 3 5

예제 출력 1

17
12

예제 입력 A

1 1 2
5000000000000000000
2 1 1
1 1 -5000000000000000000
2 1 1

예제 출력 A

5000000000000000000
-5000000000000000000

예제 입력 B

5 2 2
1
2
3
4
5
1 3 6
2 2 5
1 3 7
2 2 5

예제 출력 B

17
18

출처

• 문제의 오타를 찾은 사람: 79brue, keunbum, Nyan101, tncks0121
• 빠진 조건을 찾은 사람: 79brue, djm03178, jh05013
• 데이터를 추가한 사람: eric00513, klm03025, yuja
• 잘못된 조건을 찾은 사람: WeissBlume

알고리즘 분류

• 자료 구조
• 세그먼트 트리

---

참고 자료

세그먼트 트리를 이해하는데 아래의 강의와 링크에 많은 도움을 받았다.

https://blog.garybricks.com/segment-tree-introduction-in-c

통과된 코드

세그먼트 트리(Segment Tree)를 이용하여 구간합을 구하는 문제

#include <iostream>
using namespace std;
typedef long long ll;
int _N, _M, _K;
int _SegSize, _Num;
ll* _Numbers;
ll* _SegmentTree;

void InitSegTree()
{
    _Num = 1;
    while (_Num < _N)
        _Num *= 2;
    _SegSize = _Num * 2;
    _SegmentTree = new ll[_SegSize]();
    for (int i = _Num, j = 0; j < _N; j++)
        _SegmentTree[i + j] = _Numbers[j + 1];
    for (int i = _SegSize / 2 - 1; i > 0; i--)
        _SegmentTree[i] = _SegmentTree[i * 2] + _SegmentTree[i * 2 + 1];
}

void Update(int _Index, long long Value)
{
    _Index += _SegSize / 2 - 1;
    _SegmentTree[_Index] = Value;
    while (_Index != 0) {
        _Index /= 2;
        _SegmentTree[_Index] = _SegmentTree[_Index * 2] + _SegmentTree[_Index * 2 + 1];
    }
}

ll Sum(int _s, int _e)
{
    ll _Res = 0;
    while (_s <= _e) {
        if (_s % 2 == 1)
            _Res += _SegmentTree[_s];
        if (_e % 2 == 0)
            _Res += _SegmentTree[_e];
        _s = (_s + 1) / 2;
        _e = (_e - 1) / 2;
    }
    return _Res;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> _N >> _M >> _K;
    _Numbers = new ll[_N + 1]();
    for (int i = 1; i <= _N; i++)
        cin >> _Numbers[i];
    InitSegTree();

    ll _t1, _t2, _O;
    while (_M + _K > 0) {
        cin >> _O >> _t1 >> _t2;
        if (_O == 1) {
            Update(_t1, _t2);
            _M--;
        }
        else if (_O == 2) {
            cout << Sum(_t1 + _Num - 1, _t2 + _Num - 1) << "\n";
            _K--;
        }
    }
    return 0;
}