213. IMOS Method

펜윅 트리를 설명하면서 연습문제로 수열과 쿼리 21을 소개했다. 그리고 문제 해설에 구간 업데이트 + 점 쿼리를 점 업데이트 + 구간 쿼리로 변형할 수 있다고 했는데, 이 아이디어를 정형화한 IMOS법(IMOS Method)에 대해서 알아보기로 한다.

 

IMOS법은 구간을 시작점과 끝점으로 분리하여 구간 처리를 점 처리로 대체하는 트릭으로, 구간이 여러 개 주어지고 특정 시점을 포함하는 구간의 수를 빠르게 구할 수 있는 방법이다. 수식을 써서 표현하면 다음과 같이 나타낼 수 있다.

• 구간 $n$개가 존재하며, $i$번째 구간을 $[l_i, r_i]$로 나타낼 수 있다. $(l_i \le r_i)$
• $k$를 포함하는 구간의 수를 구하는 쿼리가 주어진다.

여기서는 $l_i$와 $r_i$가 모두 $1$ 이상 $2n$ 이하로 충분히 작은 범위에 있는 경우만 고려하기로 한다. $l_i$와 $r_i$의 범위가 큰 경우 좌표 압축을 하면 범위가 작은 경우와 같아진다.

---

IMOS법을 적용할 수 있는 경우는 구간이 전부 주어지고 그 다음에 쿼리를 처리해야 하는 경우이다. (쿼리가 주어지다가 중간에 구간이 추가되는 등 쿼리가 나오는 시점이 무작위인 경우 이는 사실상 수열과 쿼리 21과 동일한 문제로 펜윅 트리 등을 이용해서 풀어야 한다.) 앞서 $i$번째 구간을 $[l_i, r_i]$로 나타낼 수 있다고 했는데, 여기서 시작점인 $l_i$와 끝점인 $r_i$만 추출하면 총 $2n$개의 지점이 나오게 된다(어떤 지점들은 서로 겹칠 수 있다). 이것들을 누적합으로 처리하면 되는데 어떤 식으로 하는지 예시를 통해 알아보기로 한다.

 

다음과 같이 $5$개의 구간이 있다고 하자.

$$[7, 10], [6, 7], [1, 5], [3, 6], [5, 10]$$

각각의 좌표는 칸(Cell)을 나타낸다고 가정한다. (어떤 문제에서는 좌표가 점(Point)을 나타낼 수도 있는데, 이 경우의 처리 방법은 뒤에서 설명한다.) 그러면 위의 구간을 다음과 같이 그림으로 나타낼 수 있다.

이제 구간을 누적합을 구할 수 있는 형태로 변환해야 한다. 앞에서 누적합을 설명할 때 두 누적합의 차이를 이용해서 구간 합을 구할 수 있다고 했는데, 이를 이용하면 각 구간마다 다음과 같은 방식으로 값을 더해 주면 된다는 것을 알 수 있다.

시작점에 $+1$, 끝점의 다음 지점에 $-1$을 더한다. 그리고 나서 칸마다 누적합을 구하면 구간이 포함된 지점들에만 $1$씩 더해지는 결과가 된다. 이제 같은 작업을 구간마다 다 해주면 된다. 누적합은 마지막에 한 번만 하면 되고 구간의 수가 $n$이므로 $\Theta(n)$ 시간에 누적합이 전부 구해진다.

 

좌표가 점을 나타내는 경우는 어떻게 다른지 살펴보자. 이 경우 $i$번째 구간의 엄밀한 표기는 $(l_i, r_i)$가 된다. 앞에서 좌표가 칸을 나타내는 경우는 $l_i = r_i$여도 $1$칸짜리 구간이 되므로 아무 문제가 없었지만 이번에는 $l_i = r_i$이면 구간이 아무것도 포함하지 않게 되므로 좌표가 점을 나타내는 경우에는 $l_i < r_i$인 구간만 생각하기로 한다. 구간 $(l_i, r_i)$가 완전히 포함하는 점은 $(l_i + 1)$부터 $(r_i - 1)$까지이므로 $(l_i, r_i)$를 $[l_i + 1, r_i - 1]$로 생각하면(둘은 분명히 다르다. '바꾸면'이라는 표현을 쓰지 않은 이유가 있다.) 비슷하게 누적합을 구할 수 있다.

---

IMOS법의 장점은 $1$차원 구간뿐 아니라 다른 형태에도 적용이 가능하다는 것이다. $2$차원에서는 IMOS법을 어떻게 적용하는지 알아보자.

이렇게 생긴 그리드에서 각각의 칸을 포함하는 직사각형의 수를 구해 보기로 한다. 왼쪽 위가 원점이라고 가정한다.

누적합에 관한 글을 다시 보면 네 귀퉁이의 값을 이용해 누적합을 계산한다. 이것을 바탕으로 $1$차원 구간에서 IMOS법을 적용한 방법을 확장하면 다음과 같이 하면 된다는 것을 알 수 있다.

이렇게 하고 누적합을 구하면 직사각형이 포함하는 칸들에만 $1$씩 더해지는 결과가 된다.

그밖에도 다양한 형태의 IMOS법이 존재한다.

 

구현은 다음과 같다.

------------------------------------------------------------
#import<bits/stdc++.h>
using namespace std;
int a[200004];
int main()
{
    int l, n, r;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> l >> r;
        a[l]++;
        a[r + 1]--;
    }
    for(int i = 1; i <= 2 * n; i++)a[i] += a[i - 1];
}
------------------------------------------------------------
#import<bits/stdc++.h>
using namespace std;
int a[2004][2004];
int main()
{
    int lx, ly, n, rx, ry;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> lx >> ly >> rx >> ry;
        a[lx][ly]++;
        a[lx][ry + 1]--;
        a[rx + 1][ly]--;
        a[rx + 1][ry + 1]++;
    }
    for(int i = 1; i <= 2 * n; i++)
    {
        for(int j = 1; j <= 2 * n; j++)a[i][j] += a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];
    }
}
------------------------------------------------------------

 

[연습문제] (1차원 IMOS법 연습문제들 추천받습니다.)

 

BOJ 25826. 2차원 배열 다중 업데이트 단일 합 (Gold IV)

$2$차원 IMOS법 기본 문제이다.