Imos Algorithm

• Imos Law - いもす法
• 구간합 압축 버전
• 누적합 기반 구간 처리법
  • [a, b]
    • arr[a] = 1
    • arr[b] = -1 or arr[b + 1] = -1
    • psum 하면 전체 구간 상태 도출
  • 좌표 압축과 활용하면 효율 더 향상
    • 들어온 좌표만 기록해서, 해당 좌표를 인덱스로 치환
    • 좌표의 최소, 최대 값 격차가 커도, 인덱스로 관리 가능
  • 정해진 구간 내에 시작과 끝이 포함된 부분 집합에 대한 명령이 여러개(누적하여) 들어올 때 효율적

•   int imos[SIZE + 2];
    
    // [l, r]
    imos[l] += 1;
    imos[r] -= 1; or imos[r + 1] -= 1;
    
    // psum
    for (int i = 1; i <= n; i++) {
        imos[i] += imos[i - 1];
    }