[백준] 14245 XOR

14245번: XOR

문제 확인

 

구간 업데이트 처리 문제입니다.

세그먼트 트리를 활용해서 풀 수 있지만 점 쿼리 처리에 특화된 펜윅트리를 사용하여 더욱 빠르게 풀 수 있습니다.

펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)

 

풀이

 

펜윅트리를 적용하면 간단하게 풀 수 있는 문제입니다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;
int n, m;
int ary[500001];
 
inline void update(int i, int val) {
    for (; i <= n; i += i & -i)
        ary[i] ^= val;
}
inline int query(int i) {
    int t = 0;
    for (; i; i -= i & -i)
        t ^= ary[i];
    return t;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    cin >> n;
    for (int i = 0, t; i < n; i++) {
        cin >> t;
        update(i + 1, t);
        update(i + 2, t);
    }
 
 
    cin >> m;
    while (m--) {
        int op;
        cin >> op;
        if (op != 2) {
            int s, e, v;
            cin >> s >> e >> v;
            update(s + 1, v);
            update(e + 2, v);
        }
        else {
            int i;
            cin >> i;
            cout << query(i + 1) << '\n';
        }
    }
}