소프티어

import java.io.*;
import java.util.*;

public class Main {
   
    static int N, K;
    static int [] scoreSum;
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        scoreSum = new int[N+1];

        st = new StringTokenizer(bf.readLine());
        for(int i=1; i<=N; i++) {
            scoreSum[i] = scoreSum[i-1] + Integer.parseInt(st.nextToken()); 
        }
        
        StringBuilder sb = new StringBuilder();
        
        for(int i=0; i<K; i++) {
            st = new StringTokenizer(bf.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            sb.append(String.format("%.2f",getAvg(from, to))).append("\n");
        }

        System.out.println(sb);
    }

    private static double getAvg(int from, int to) {
        double sum = (to - from) + 1;
        return (double)(scoreSum[to] - scoreSum[from-1]) / sum ;
    }
}

구간을 입력받아서 해당 구간에 속하는 성적들을 다 더해서 갯수로 나누어주는 방식을 이용하면

구간의 길이가 L이라고 할 때,

성적 조회 -> O(L)의 시간 복잡도를 가지고,

따라서, K*O(L)로 약 O(N^2) 시간 복잡도를 가지게 됩니다.

하지만, 누적합을 이용하면

구간([a, b])에 대한 성적을 모두 더하는 것이 아닌, 누적합[b] - 누적합[a-1] 방식으로 O(1) 시간에 성적합을 구할 수 있습니다.

따라서, O(K)로 효율적으로 평균을 구할 수 있습니다.