CS/ALGORITHM1 누적합, imos 법 참고: https://driip.me/65d9b58c-bf02-44bf-8fba-54d394ed21e0 누적합 모든 입력을 다 받았을 때, i번째 인덱스 까지의 합을 미리 구해두면 (a, b) 구간합 빠르게 구할 수 있음 def accsum(arr): tmp = [arr[0]] for a in arr: tmp.append(tmp[-1]+a) return tmp imos 법 (a, b) 구간의 값을 자주 변경 할 때, 하나씩 처리하지 않고 시작과 끝만 기록해둔 후 모든 입력을 다 받은 후 갱신 어떤 구간에 쿼리(a, b)가 가장 많이 겹치는가 하는 문제에서 활용가능 # queries = (a, b, value) * n imos = [0 for _ in range(len(arr)+1)] for query i.. 2021. 9. 13. 이전 1 다음