[백준 파이썬] 11505 구간 곱 구하기

백준 2357

여기에 있는 강의를 바탕으로 구현했다.

N, M, K = map(int, input().split())
arr = [int(input()) for _ in range(N)]
changes = [list(map(int, input().split())) for _ in range(M+K)]

## 세그먼트 트리 리스트 초기화
# 주어진 리스트의 길이보다 긴 2의 거듭제곱 길이만큼 리스트 생성
length = 0
while 2**length < N:
    length += 1
length = 2**length

# 곱을 저장하므로 1로 초기화
seg_tr = [1 for _ in range(length*2)]

# 전체 길이의 절반 위치부터 입력 값들을 새 리스트에 저장
for idx in range(N):
    seg_tr[length + idx] = arr[idx]

# 범위를 줄여가면서 같은 부모 노드를 가지는 두 자식 노드로 부모 노드 업데이트
rng = length
while rng > 1:
	# 길이가 16이라면 8번째 인덱스와 9번째 인덱스의 곱이 4번째 인덱스로,
    # 길이를 절반으로 줄이고 다시 반복해서 1번 인덱스까지 반복한다
    for idx in range(rng//2, rng):
        seg_tr[idx] = (seg_tr[idx*2] * seg_tr[idx*2 + 1]) % 1_000_000_007
    rng //= 2


for a, b, c in changes:
    rng = length
    
 	# 배열의 수를 바꾸는 경우
    if a == 1:
    	# 세그먼트 트리에 맞는 범위로 인덱스 수정
        b = rng + b - 1
        # 해당하는 인덱스 값 수정
        seg_tr[b] = c

        while b > 1:
        	# 처음 세그먼트 트리를 초기화 할 때처럼 부모 노드 업데이트
            # 바뀐 노드의 부모 노드들만 바꿔주면 된ㅏ
            if b%2 == 0:
                seg_tr[b//2] = (seg_tr[b] * seg_tr[b+1]) % 1_000_000_007
            else:
                seg_tr[b//2] = (seg_tr[b] * seg_tr[b-1]) % 1_000_000_007
            b //= 2

	# 출력하는 경우
    if a == 2:
        ans = 1
		
        # 범위 수정
        b = rng + b - 1
        c = rng + c - 1

		# 시작 노드가 끝나는 노드와 같거나 작을 동안
        while b <= c:
        	# 시작 노드의 부모노드가 포함되지 않고 현재 노드만 포함된다면
            if b%2 == 1:
            	# 바로 적용
                ans *= (seg_tr[b] % 1_000_000_007)
            # 부모 노드가 포함되는 된다면 바로 부모 노드로, 
            # 포함되지 않는다면 인덱스가 더 큰 오른쪽 노드의 부모 노드로 가하므로
            # 1을 더하고 부모 노드로 이동
            b = (b+1) // 2
			
            # 끝 노드에도 마찬가지로 적용하지만,
            # 끝 노드는 시작 노드와 반대 방향으로 이동하므로 부모노드가 포함되지 않는다면
            # 1을 빼주고 부모 노드로 이동
            if c%2 == 0:
                ans *= (seg_tr[c] % 1_000_000_007)
            c = (c-1) // 2
        
        print(ans % 1_000_000_007)