1/17
Loading...
📚구간 질의가 여러 번!
일별 방문자: [5, 8, 6, 3, 7, 9, 4] 사서들이 "l일~r일 합?"을 하루에도 수십 번 묻습니다. 매번 더하면 너무 느려요!
Loading...
일별 방문자: [5, 8, 6, 3, 7, 9, 4] 사서들이 "l일~r일 합?"을 하루에도 수십 번 묻습니다. 매번 더하면 너무 느려요!
당신은 동네 도서관의 운영 담당자입니다. 요일별 방문자 수가 기록된 배열이 주어지고, 사서들이 "l번째 날부터 r번째 날까지 총 몇 명이 왔나요?" 같은 질문을 하루에도 수십 번씩 합니다. 질문이 들어올 때마다 처음부터 더하면 너무 느립니다. 미리 누적합 배열을 만들어 두면, 어떤 구간이든 뺄셈 한 번으로 즉시 답할 수 있습니다.
visitors = [5, 8, 6, 3, 7, 9, 4], queries = [[2, 5], [0, 2], [4, 6]]
[25, 19, 20]
누적합: prefix = [0, 5, 13, 19, 22, 29, 38, 42] • [2, 5]: prefix[6] - prefix[2] = 38 - 13 = 25 (6+3+7+9) • [0, 2]: prefix[3] - prefix[0] = 19 - 0 = 19 (5+8+6) • [4, 6]: prefix[7] - prefix[4] = 42 - 22 = 20 (7+9+4)
visitors = [10, 0, 4, 6], queries = [[0, 3], [1, 1]]
[20, 0]
누적합: prefix = [0, 10, 10, 14, 20] • [0, 3]: prefix[4] - prefix[0] = 20 - 0 = 20 (전체 합) • [1, 1]: prefix[2] - prefix[1] = 10 - 10 = 0 (휴관일!)