알고리즘 - 누적합

문제 링크 - 백준 11659번

참조 해설 링크 - 백준 알고리즘 누적합

1. 가장 생각하기 쉬운 방법

• 소스 1

  int ans = 0;
  for (int i=l; i<=r; i++) {
      ans += a[i];
  }

  이것의 시간 복잡도는 O(N)이고, 연산을 M번 하므로 총 시간 복잡도는 O(NM)이다.

2. 누적합

• 배열 A에 들어있는 값은 바뀌지 않으므로 구간의 합도 변하지 않는다.

• 이를 이용해 누적합의 배열을 만들어 놓고 이것으로 구간의 합을 구할 수 있다.

• l번째 수부터 r번째 수까지 합 = S[r] - S[l-1]

• 이것을 구하기 위해 뺄셈 한 번만 하면 되니 시간복잡도는 O(1)이고, 연산을 총 M번 하므로 총 시간 복잡도는 O(M)이 된다.

• 부분합을 구하는 코드

  for (int i=1; i<=n; i++) {
      s[i] = s[i-1] + a[i];
  }

• 최종 코드

  package cumulativesum;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.StringTokenizer;
  
  public class No11659 {
  
      public static void main(String[] args) throws Exception {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  
          StringTokenizer st = new StringTokenizer(br.readLine(), " ");
          StringBuilder sb = new StringBuilder();
          int n = Integer.parseInt(st.nextToken());
          int m = Integer.parseInt(st.nextToken());
  
          int[] arr = new int[n+1];
          int[] s = new int[n+1];
          st = new StringTokenizer(br.readLine());
  
          for (int i = 1; i < arr.length; i++) {
              arr[i] = Integer.parseInt(st.nextToken());
              s[i] = s[i-1]+arr[i];
          }
  
          for (int i = 0; i < m; i++) {
              st = new StringTokenizer(br.readLine(), " ");
              int lt = Integer.parseInt(st.nextToken());
              int rt = Integer.parseInt(st.nextToken());
              sb.append(s[rt]-s[lt-1]+"\n");
          }
  
          System.out.println(sb.toString());
      }
  }