누적합, 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 in queries:
    a, b, value = query
    imos[a] += value
    imos[b+1] -= value

accusum(imos)

2d array

• (y1,x1), (y2,x2) 까지의 직사각형 구간을 변경한다고 할 때
• (y1,x1) = value, (y1,x2+1) = -value,
• (y2+1,x1) = -value, (y2+1,x2+1) = value 로, 각 모서리를 기록
• 이후 오른쪽으로 한번, 아래쪽으로 한번 누적합을 구해주면 된다.