테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== XOR ======

===== 풀이 =====
  * [[ps:problems:boj:12844|XOR]]과 제목이 똑같지만, 다른 문제이다. 그쪽은 구간 업데이트/구간 쿼리.
  * 구간합 업데이트/포인트 쿼리 문제의 [[ps:구간 쿼리#구간 XOR 쿼리]] 버전.
  * XOR 연산은 합 연산과 거의 비슷한 특성을 지니므로, 구간 합의 테크닉을 거의 다 적용 가능하다. 구간 합에서는, [[ps:구간 쿼리#활용 - 원소의 값을 구간합으로 처리|인접한 원소의 차를 갖고서 새로운 배열을 만드는 테크닉]]으로 이러한 문제를 포인트 업데이트/구간 쿼리로 변형해서 lazy propagation을 쓰지 않고도 문제를 풀수 있는데, XOR도 똑같은 방법을 적용할수 있다.
  * 같은 방법을 적용해서, 포인트 업데이트/구간 쿼리로 변형해서 Xor 펜윅트리를 갖고 풀게 되면 시간 복잡도는, 펜윅트리 구축에 O(n), m개의 쿼리를 O(logn)에 처리하는 데에 O(mlogn), 합쳐서 O(n+mlogn)이 된다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 14245. XOR".

- Problem link: https://www.acmicpc.net/problem/14245
- Solution link: http://www.teferi.net/ps/problems/boj/14245
"""

import sys
from teflib import fenwicktree


def main():
    n = int(sys.stdin.readline())
    nums = [int(x) for x in sys.stdin.readline().split()]
    fenwick = fenwicktree.XorFenwickTree(n + 1)

    m = int(sys.stdin.readline())
    for _ in range(m):
        query = [int(x) for x in sys.stdin.readline().split()]
        if query[0] == 1:
            _, a, b, c = query
            fenwick.update(a, c)
            fenwick.update(b + 1, c)
        else:
            _, a = query
            print(fenwick.query(0, a + 1) ^ nums[a])


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:fenwicktree#XorFenwickTree|teflib.fenwicktree.XorFenwickTree]]

{{tag>BOJ ps:problems:boj:플래티넘_4}}