깃발춤 (백준 17400)

안녕하세요. 오늘은 깃발춤을 출 거예요.

문제

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

아이디어

i가 짝수이면 arr값을 -해서 넣어줍니다.
그리고 합 세그먼트 트리를 만들어줍니다.
이제 1 a b가 나오면 a부터 b까지의 합의 절댓값을 출력해주면 되고, 2 a b가 나오면 똑같이 a가 짝수이면 -b를 넣어서 트리값을 갱신해주면 됩니다.

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

ll tree[1212121] = { 0 }, arr[303030] = { 0 };
ll init(ll s, ll e, ll node)
{
    if (s == e) return tree[node] = arr[s];
    ll mid = (s + e) / 2;
    return tree[node] = init(s, mid, node * 2) + init(mid + 1, e, node * 2 + 1);
}
ll SUM(ll s, ll e, ll node, ll l, ll r)
{
    if (e < l || r < s) return 0;
    if (l <= s && e <= r) return tree[node];
    ll mid = (s + e) / 2;
    return SUM(s, mid, node * 2, l, r) + SUM(mid + 1, e, node * 2 + 1, l, r);
}
void change(ll s, ll e, ll node, ll idx, ll val) //idx에 val만큼 더하기
{
    if (e < idx || idx < s) return;
    tree[node] += val;
    if (s == e) return;
    ll mid = (s + e) / 2;
    change(s, mid, node * 2, idx, val);
    change(mid + 1, e, node * 2 + 1, idx, val);
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, M, i, a, b, c;
    cin >> N >> M;
    for (i = 1; i <= N; i++)
    {
        cin >> arr[i];
        if (i % 2 == 0) arr[i] = -arr[i];
    }
    init(1, N, 1);

    for (i = 0; i < M; i++)
    {
        cin >> a >> b >> c;
        if (a == 1) cout << abs(SUM(1, N, 1, b, c)) << "\n";
        else
        {
            if (b % 2 == 0) c = -c;
            change(1, N, 1, b, c);
        }
    }
}

감사합니다.