7304 : 재귀 세그먼트 트리
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
세그먼트 트리(Segment Tree)는 배열의 구간 합/최댓값 등을 $O(\log N)$에 계산하고 업데이트할 수 있는 트리 자료구조입니다.
재귀적으로 세그먼트 트리를 구현하여 구간 합 쿼리와 점 업데이트를 처리하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
재귀적으로 세그먼트 트리를 구현하여 구간 합 쿼리와 점 업데이트를 처리하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 원소 수 $N$, 업데이트 수 $M$, 구간합 쿼리 수 $K$가 주어집니다.
둘째 줄에 $N$개의 초기 원소가 주어집니다.
이어서 $M+K$개의 줄에 명령어가 주어집니다.
-
-
둘째 줄에 $N$개의 초기 원소가 주어집니다.
이어서 $M+K$개의 줄에 명령어가 주어집니다.
-
1 i v: $i$번째 원소를 $v$로 업데이트-
2 l r: $l$번째부터 $r$번째까지의 합을 출력출력 설명
구간합 질의(
2) 결과를 각 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 1 2
1 2 3 4 5
1 3 10
2 1 5
2 2 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
22
16도움
세그먼트 트리 노드 번호 $k$의 왼쪽 자식은 $2k$, 오른쪽 자식은 $2k+1$입니다. 쿼리 범위와 현재 노드 범위를 비교하여 재귀적으로 탐색합니다.