[백준 14245] XOR

문제

www.acmicpc.net/problem/14245

 

알고리즘

fenwick

 

풀이

구간 업데이트와 점 쿼리를 처리하는 문제입니다.

 

일반적인 펜윅트리는 점 갱신과 구간 쿼리를 처리하는 용도로 많이 사용됩니다. 구간 갱신을 사용하기 위해서는 일반적으로 lazy propagation을 떠올리기 쉽습니다.

 

하지만 구간 갱신을 처리하더라도 쿼리가 구간 쿼리가 아닌 점 쿼리만 이루어진다면 일반적인 펜윅트리의 변형으로도 가능합니다. 

 

일반적으로 펜윅트리에서 배열 $A$에 대해 우리가 하는 연산은 다음과 같습니다.

 

$update(i,v)$ = $A[i]$에 $v$만큼 더하기

$query(i)$ = $A[1]$~$A[i]$까지 합 구하기

 

다음과 같은 $B$배열을 만들면 구간 갱신과 점 쿼리가 가능합니다.

 

$B[i]$=$A[i]-A[i-1]$

 

즉 $B$배열에 $query(i)$를 사용하여 A[1]-A[0] + A[2]-A[1] ··· A[i]-A[i-1] = A[i] ( A[0]은 사용하지 않으므로 0 으로 초기화 합니다) 를 한번에 구할 수 있고

 

$update(l,v)$ $update(r+1,-v)$ 을 살펴보면 A[l] - A[l-1]은 v만큼 커지고 A[l+1]-A[l]은 구간 갱신이 일어났으므로 변화가 없습니다. 계속 진행하여 A[r+1] -A[r]은 구간 갱신이 끝나는 부분이므로 다시 -v만큼 차이가 발생해야 합니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

int N, Q;
int tree[500005];

void update(int idx, int v) {
    for (; idx <= N; idx += idx & -idx)
        tree[idx] ^= v;
}
int query(int idx) {
    int ret = 0;
    for (; idx; idx -= idx & -idx)
        ret ^= tree[idx];
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N;
    rep(i, N) {
        int x;
        cin >> x;
        update(i + 1, x);
        update(i + 2, x);
    }
    cin >> Q;
    while (Q--) {
        int t, a, b, c;
        cin >> t;
        if (t == 1) {
            cin >> a >> b >> c;
            update(a + 1, c);
            update(b + 2, c);
        } else {
            cin >> a;
            cout << query(a + 1) << '\n';
        }
    }
    return 0;
}