흙금이네 블로그

아이디어 세그먼트 트리로 구간 곱을 저장해두고 변경이나 계산이 필요한 구간에 대해 빠르게 처리한다. 풀이 2042번 구간 합 구하기 문제와 유사한 문제로, 합이 아닌 곱을 저장하면 된다. 구간 곱을 계산하기 위해 N보다 크면서 가장 작은 2의 거듭제곱의 두 배 크기로 1로 채워진 리스트 tree를 만든다. 트리의 리프 노드들에는 순서대로 N개의 수를 입력 받고, for문에서 각 부모 노드에 두 자식 노드의 곱을 저장한다. 이후 for문에서는 a가 1이라면 해당 트리 리프 노드의 수를 변경한 후 함수 update를, a가 2라면 함수 multiply를 호출한다. 함수 update에서는 리프 노드의 부모 노드부터 루트 노드까지 다시 계산하고, 재귀 호출로 루트 노드를 벗어나면 종료한다. 함수 multiply..