[ 백준 ] 17400번 - 깃발춤 (C++)

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

17400번: 깃발춤

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/51

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

 

1. 번갈아가면서 춤을 추므로 segmentTree[ node ].first에는 idx % 2 == 0인 값을 second에는 idx % 2 == 1인 값을 넣어줍니다.

 

[ 소스코드 ]

#include<iostream>
#include<cmath>
#define ll long long
using namespace std;
 
int N, Q;
int arr[300001];
pair<ll, ll> segTree[1050000];
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        if (s % 2 == 0) {
            segTree[node].first = arr[s];
        }
        else {
            segTree[node].second = arr[s];
        }
        return;
    }
 
    int m = (s + e) / 2;
 
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    segTree[node].first = segTree[node * 2].first + segTree[node * 2 + 1].first;
    segTree[node].second = segTree[node * 2].second + segTree[node * 2 + 1].second;
}
 
pair<ll,ll> getTree(int node, int s, int e, int sidx, int eidx)
{
    if (eidx < s || e < sidx) return { 0,0 };
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
 
    pair<ll, ll> left = getTree(node * 2, s, m, sidx, eidx);
    pair<ll, ll> right = getTree(node * 2 + 1, m+1, e, sidx, eidx);
    
    return { left.first + right.first, left.second + right.second };
}
 
void updateTree(int node, int s, int e, int idx, int x)
{
    if (s > idx || e < idx) return;
    if (idx % 2 == 0) {
        segTree[node].first += x;
    }
    else {
        segTree[node].second += x;
    }
 
    if (s != e) {
        int m = (s + e) / 2;
 
        updateTree(node * 2, s, m, idx, x);
        updateTree(node * 2 + 1, m + 1, e, idx, x);
    }
}
 
int main()
{
    scanf("%d %d", &N, &Q);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    for (int i = 0; i < Q; i++) {
        int com, L, R;
        scanf("%d %d %d", &com, &L, &R);
 
        if (com == 1) {
            pair<ll, ll> temp = getTree(1, 1, N, L, R);
            printf("%lld\n", abs(temp.first - temp.second));
        }
        else {
            updateTree(1, 1, N, L, R);
        }
    }
}