BOJ 17203 - ∑|ΔEasyMAX| 링크
(2023.09.11 기준 S4)

문제

노래의 길이 N초와 초당 박자 빠르기가 N개 주어진다.

박자 빠르기의 변화량의 합을 구하고자 하는 Q개의 구간이 주어질 때마다 알맞게 출력

알고리즘

값의 변경이 없는 조건 하에 구간의 합을 빠르게 구하는 방법은 누적 합

풀이

먼저 N개의 박자의 인접한 박자의 차 N-1개를 담은 배열 A를 구하자. 변화량을 구해야 하니깐.
그리고 N-1개로 하여금 누적 합 배열 prefix_sum을 만들자.

A[i]는 a[i-1] ~ a[i]의 변화량을 담고 있다.
만약에 구간 [1, 3]의 변화량의 합을 구해야 한다면? a[1] ~ a[3]의 변화량의 합을 구해야 하므로 [A[2], A[3]]의 합 = prefix_sum[3] - prefix_sum[1]을 구하면 된다.

일반적인 누적 합을 이용한 구간 합 쿼리 [l, r]은 prefix_sum[r] - prefix_sum[l-1]을 구하지만, 이 문제는 점마다 한 구간을 담았으므로. 즉, A[i] = (a[i-1], a[i]] 구간이므로 prefix_sum[l-1]이 아닌 prefix_sum[l]을 빼줘야 한다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, Q; cin >> N >> Q;
    int a[N]; for (int i = 0; i < N; i++) cin >> a[i];

    // 인접 원소의 차
    int A[N];
    for (int i = 1; i < N; i++) A[i] = abs(a[i] - a[i - 1]);

    // 인접 원소의 차의 누적 합
    int prefix_sum[N]; prefix_sum[0] = 0;
    for (int i = 1; i < N; i++) prefix_sum[i] = prefix_sum[i - 1] + A[i];

    for (int l, r; Q; Q--){
        cin >> l >> r;

        // 구간 합은 누적 합의 차로 나타낼 수 있다.
        // ~ l ~ l+1 ~ ... ~ r-1 ~ r ~ ...
        cout << prefix_sum[--r] - prefix_sum[--l] << '\n';
    }
}

• Python

import sys; input = sys.stdin.readline

N, Q = map(int, input().split())
a = list(map(int, input().split()))

# 인접 원소의 차
A = [0] * N
for i in range(1, N):
    A[i] = abs(a[i] - a[i - 1])

# 인접 원소의 차의 누적 합
prefix_sum = [0] * N
for i in range(1, N):
    prefix_sum[i] = prefix_sum[i - 1] + A[i]

for _ in range(Q):
    l, r = map(int, input().split())
    l -= 1; r -= 1

    # 구간 합은 누적 합의 차로 나타낼 수 있다.
    # ~ l ~ l+1 ~ ... ~ r-1 ~ r ~ ...
    print(prefix_sum[r] - prefix_sum[l])