XOR

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

"""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()

• Dependency: teflib.fenwicktree.XorFenwickTree