영속 세그먼트 트리

문제

$N$개의 정수로 이루어진 배열이 주어진다. 다음 두 종류의 쿼리를 처리하는 프로그램을 작성하라. 이 문제는 쿼리 1이 실행될 때마다 기존 배열을 변경하는 것이 아니라 새로운 버전의 배열을 만들어내는 영속 세그먼트 트리(Persistent Segment Tree)를 구현하여 해결할 수 있다.

• 1 v i x: $v$번 버전의 배열에서 $i$번째 원소를 $x$로 바꾼 새로운 버전을 만든다. 새로운 버전의 번호는 이전까지 만들어진 가장 큰 버전 번호에 1을 더한 값이 된다.
• 2 v i: $v$번 버전의 배열에서 번째 원소를 출력한다.