누적합의 확장 IMOS

IMOS는 누적합의 개념으로 특정 구간에서 가장 많이 중첩되는 영역을 구할 수 있는 방법 중 하나이다.

예를 들어 가게에 Q명의 손님이 방문한다. 가게는 시간 0부터 T까지 운영되며, 각각의 손님 i의 방문 시각(si)과 퇴장 시각(ei)이 입력으로 주어진다. 가게 운영 중 손님이 가장 많이 방문했을 때의 손님 수는 몇 명인가?

이런 문제가 있다면 입력을 위와 같은 그림으로 나타낼 수 있을 것이다.
이 때 가장 단순하게 구현한다면 for문을 si부터 ei까지 돌리면서 해당 배열의 값을 +1 해주는 것이겠지만 이 경우는
쿼리 하나의 처리 시간이 T 쿼리의 갯수를 Q라고 했을 때 시간 복잡도는 Q(TQ)가 되어서
쿼리가 많아지고 시간이 길어지는 경우에는 풀 수 없게된다.

 

이 때 사용하는 IMOS는 입장과 퇴장에 대한 정보만 기록하는 것이다.
입장하는 시간에 +1 퇴장하는 시간에 -1을 하는 것으로 마지막에 답을 구할 때, 처음부터 내가 원하는 시간까지의 합을 구하면 O(T)로 구할 수 있게된다.

입장 시각 +1, 퇴장 시각 -1

쿼리 하나당 처리 시간 O(1)의 시간이 소요되고 후에 계산은 T만큼 걸리기 때문에 O(Q + T)의 시간이 걸린다.

 

누적합과의 비교

누적합의 경우는 입력을 다 받고, 1번의 전처리로 데이터를 완성하기 때문에 쿼리가 데이터의 값을 갱신하지 않는다.
imos는 각 쿼리가 구간의 값을 갱신하는 경우에 매 쿼리마다 갱신하는 것이 아니라 데이터가 필요한 순간에
계산하여 사용하는 방식이다.

 

 

출처

https://driip.me/65d9b58c-bf02-44bf-8fba-54d394ed21e0

누적합의 확장, imos법