2042번: 구간 합 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
분석
세그먼트 트리, 인덱스 트리, 구간합
1. 세그먼트 트리 주어진 데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조 2. 구간합 합배열(prefix sum)은 업데이트가 느림 arr[1]를 update 한다면 ? sum[1]부터 sum[9]까지
karla.tistory.com
풀이
1. 트리 초기화하기 ➔ setTree(idx)
트리 크기(treeSize) = 2^(K+1) = 2^(treeHeight+1)
원본데이터 시작 인덱스(리프노드) = 2ᵏ
부모노드 인덱스 = 2 ~ 2ᵏ-1
leftStartIdx = 2ᵏ-1 = treeSize // 2 - 1 = 2ᵏ * 2 // 2 - 1
2. 질의값 구하기 ➔ 주어진 질의 인덱스를 세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경
b = leftStartIdx + b
c = leftStartIdx + c
3. 업데이트 하기 ➔ changeVal(idx, val)
diff 변경값 저장
2ᵏ 번 연산 수행
4. 구간합 구하기 ➔ getSum(sIdx, eIdx)
노드가 독립노드로 선택된 경우 합계에 더하고 구간내 인덱스로 이동 후 부모 노드로 이동
선택: 해당 노드의 부모가 나타내는 범위가 질의 범위를 넘어가기 때문에 해당 노드를 독립 노드로 선택
"""
구간합 구하기3
N개의 수(1~1,000,000)
중간에 수의 변경이 빈번히 일어남, 그 중간에 어떤 부분의 합을 구함
1,2,3,4,5 -> 1,2,6,4,5 변경 -> 2~5번째 합 구하기 => 17
1,2,6,4,5 -> 1,2,6,4,2 변경 -> 3~5번쨰 합 구하기 => 12
N(1~1,000,000) 수의개수
M(1~10,000) 변경이 일어나는 횟수
K(1~10,000) 구간합
2 - N+1줄 : N개의 수
N+2 N+M+K+1줄 : 3개의 정수 a b c
1 b c : b번째 수 c로 변경
2 b c : b번째 수에서 c 번째 수까지 합 출력
"""
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
treeHeight = 0 # 트리 높이
lenth = n # 리프노드 갯수
# 높이 계산 : 리프노드의 개수를 2씩 나누면서
while lenth != 0:
lenth //= 2
treeHeight += 1
# 트리 길이 2ᵏ*2
treeSize = pow(2, treeHeight + 1)
# 리프노드 전 인덱스 2ᵏ-1 = 2ᵏ*2/2 -1
leftStartIdx = treeSize // 2 - 1
# 인덱스 트리 저장 리스트
tree = [0] * (treeSize + 1)
# 데이터를 리프노드에 저장
for i in range(leftStartIdx + 1, leftStartIdx + n + 1):
tree[i] = int(input())
# 인덱스 트리 생성 함수
def setTree(idx):
# 인덱스가 루트노드가 아닐때까지
while idx != 1:
# # 2ᵏ-1부터 2까지 부모노드 값 저장
tree[idx // 2] += tree[idx]
idx -= 1
setTree(treeSize - 1)
# 값 변경 함수
def changeVal(idx, val):
diff = val - tree[idx]
while idx > 0:
tree[idx] = tree[idx] + diff
idx //= 2
# 구간합 출력 함수
def getSum(sIdx, eIdx):
sum = 0
while sIdx <= eIdx:
if sIdx % 2 == 1: # 선택 : 부모노드 대상범위 제거, 독립노드
sum += tree[sIdx]
sIdx += 1
sIdx = sIdx // 2
if eIdx % 2 == 0: # 선택 : 부모노드 대상범위 제거, 독립노드
sum += tree[eIdx]
eIdx -= 1
eIdx = eIdx // 2
return sum
for _ in range(m+k):
a, b, c = map(int, input().split())
if a == 1:
# 변경
changeVal(leftStartIdx + b, c)
elif a == 2:
# 구간합출력
b = leftStartIdx + b
c = leftStartIdx + c
print(getSum(b, c))