수들의 합 7
시간 제한2초메모리 제한256 MB
최대 100만 개 원소 배열에서 최대 100만 번의 갱신과 구간 합 질의를 처리해야 하며, 펜윅 트리나 세그먼트 트리가 필요합니다.
문제
길이가 N인 수열 A가 있다. 처음에는 모든 원소가 0이다.
Sum(i, j)는 위치 i와 j 사이의 모든 값을 더해 반환한다. i가 j보다 크면 j부터 i까지의 합을 구한다. Modify(i, k)는 A[i]의 값을 k로 바꾼다.
M개의 명령이 순서대로 주어진다. 각 Modify 명령에 대해서는 수열을 갱신하고, 각 Sum 명령에 대해서는 반환값을 출력하는 프로그램을 작성하라.
입력
첫째 줄에 N과 M이 주어진다. (1 <= N <= 1,000,000, 1 <= M <= 1,000,000)
다음 M개의 줄에는 명령이 실행되는 순서대로 하나씩 주어진다. 각 줄의 첫 번째 수가 0이면 Sum 명령이며, 이어지는 두 수는 i와 j이다. 첫 번째 수가 1이면 Modify 명령이며, 이어지는 두 수는 i와 k이다.
처음에는 모든 i에 대해 A[i] = 0이다. Modify 명령에서 1 <= k <= 100,000이다.
출력
Sum 명령이 실행될 때마다 그 반환값을 한 줄에 하나씩 출력한다.