8051 : 구간 합 업데이트
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
길이 $N$인 정수 배열 $A$에 대해 두 종류의 쿼리를 처리하십시오.
1. 업데이트: 위치 $i$의 값에 $v$를 더합니다. (1-indexed)
2. 합 쿼리: 구간 $[l, r]$의 원소 합을 출력합니다.
[제약 조건]
• $1 \le N, Q \le 2 \times 10^5$
• $1 \le A_i \le 10^6$
• 업데이트: $1 \le i \le N$, $-10^6 \le v \le 10^6$
• 합 쿼리: $1 \le l \le r \le N$
1. 업데이트: 위치 $i$의 값에 $v$를 더합니다. (1-indexed)
2. 합 쿼리: 구간 $[l, r]$의 원소 합을 출력합니다.
[제약 조건]
• $1 \le N, Q \le 2 \times 10^5$
• $1 \le A_i \le 10^6$
• 업데이트: $1 \le i \le N$, $-10^6 \le v \le 10^6$
• 합 쿼리: $1 \le l \le r \le N$
입력 설명
첫 번째 줄에 두 정수 $N$과 $Q$ ($1 \le N, Q \le 2 \times 10^5$)가 주어집니다.
두 번째 줄에 $N$개의 정수 $A_i$ ($1 \le A_i \le 10^6$)가 주어집니다.
다음 $Q$줄에 각각 쿼리가 주어집니다.
- 업데이트:
- 합 쿼리:
두 번째 줄에 $N$개의 정수 $A_i$ ($1 \le A_i \le 10^6$)가 주어집니다.
다음 $Q$줄에 각각 쿼리가 주어집니다.
- 업데이트:
1 i v ($1 \le i \le N$, $-10^6 \le v \le 10^6$)- 합 쿼리:
2 l r ($1 \le l \le r \le N$)출력 설명
합 쿼리마다 결과를 한 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 4
1 2 3 4 5
2 1 5
1 3 10
2 1 5
2 3 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
15
25
13도움
펜윅 트리(Fenwick Tree, Binary Indexed Tree)는 점 업데이트와 구간 합 쿼리를 모두 $O(\log N)$에 처리합니다. 비트 연산
i & (-i)를 이용해 하위 비트(LSB)를 추출하여 이진 인덱스 기반 자료구조를 구성합니다.