[BOJ 16978] 수열과 쿼리 22

문제 출처 : https://www.acmicpc.net/problem/16978

 

풀이 :

세그먼트 트리 문제입니다.

 

K번째 1번 쿼리가 진행 되었을때의 A[i] ~ A[j] 구간합을 구하는 문제인데,

세그먼트 트리 자체에 K번째 까지의 진행사항을 저장하기에는 너무 많은 메모리를 요구하기 때문에 다른 방안을 찾아야 합니다.

 

그래서 우리는 쿼리를 모두 받아놓고 K번째 1번쿼리 <- 를 기준으로 2번 쿼리를 정렬한 후 K값이  증가할 때 마다 1번 쿼리를 실행 시킴으로써 빠른 속도로 쿼리를 처리할 수 있습니다.

 

이처럼 쿼리를 모두 받아놓고 쿼리를 실행시키는 것을 오프라인 쿼리라고 합니다.