[자료구조 및 알고리즘] 온라인 쿼리 vs 오프라인 쿼리

1. 온라인 쿼리

특징

• 쿼리가 주어지면 즉시 처리하고 결과를 반환해야 한다.
• 입력받은 순서대로 쿼리를 처리한다.
• 실시간 데이터 업데이트나 연속된 요청 처리가 필요한 문제에서 사용

사용해야 하는 상황

1. 실시간 응답이 필요한 경우

• 사용자가 요청할 때마다 즉시 결과를 반환해야 하는 문제
• ex) 게임 서버에서 사용자의 실시간 요청 처리

2. 데이터가 점진적으로 업데이트 되는 경우

• 데이터가 동적으로 변화하며, 각 쿼리마다 최신 상태를 반영해야 하는 문제
• ex) 배열 값이 자주 변경되고, 변경된 값을 기반으로 쿼리를 처리하는 경우

3. 데이터 크기가 작거나 중간 규모인 경우

• 매 쿼리마다 즉시 처리하더라도 성능 문제가 없는 경우

알고리즘 예시

• 세그먼트 트리
• 펜윅 트리

2. 오프라인 쿼리

특징

• 쿼리를 미리 모아서 일괄적으로 처리한다.
• 쿼리의 순서를 재정렬하거나 최적화한 후 처리할 수 있다.
• 즉시 응답할 필요가 없으므로 정렬 기반 알고리즘이나 특정 데이터 구조를 활용할 수 있다.

사용해야 하는 상황

1. 즉각적인 응답이 필요하지 않은 경우

• 쿼리를 미리 모두 받은 후, 결과를 나중에 일괄적으로 반환해도 되는 무제
• ex) 배치 처리 문제

2. 효율성이 중요한 경우

• 특정 데이터 구조나 정렬을 통해 처리 비용을 줄일 수 있을 때
• Mo's를 이용한 구간 쿼리 문제

3. 데이터가 고정적이고 업데이트가 없는 경우

• 데이터가 변경되지 않고, 정적 상태에서만 처리해야 하는 문제
• ex) 특정 구간 내 고유값 개수, 최대값, 최소값 등

4. 쿼리 간 의존성이 없는 경우

• 쿼리 순서가 중요하지 않으며, 정렬이나 최적화를 통해 효율적으로 처리할 수 있을 때

알고리즘 예시

• Mo's Algorithm
• Union-Find