05. 투포인터-누적합

투포인터 / 누적합

Summary

연속 구간 문제는 먼저 값에 음수가 있는지 확인한다.
모든 수가 양수면 투포인터, 음수가 있으면 누적합 + HashMap을 의심한다.

---

투포인터 검증 템플릿

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int target = Integer.parseInt(st.nextToken());
 
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        Arrays.sort(arr);
        int left = 0;
        int right = n - 1;
        int count = 0;
 
        while (left < right) {
            int sum = arr[left] + arr[right];
 
            if (sum == target) {
                count++;
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
 
        System.out.println(count);
    }
}

---

1차원 누적합 검증 템플릿

Warning

Java 배열은 보통 0-indexed다.
prefix[i + 1] = prefix[i] + arr[i] 형태가 안전하다.

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
 
        long[] prefix = new long[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            long value = Long.parseLong(st.nextToken());
            prefix[i + 1] = prefix[i] + value;
        }
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            sb.append(prefix[r] - prefix[l - 1]).append('\n');
        }
 
        System.out.print(sb);
    }
}

---

2차원 누적합 검증 템플릿

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
 
        long[][] prefix = new long[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= m; j++) {
                long value = Long.parseLong(st.nextToken());
                prefix[i][j] = value + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
            }
        }
 
        StringBuilder sb = new StringBuilder();
        for (int query = 0; query < q; query++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
 
            long sum = prefix[x2][y2]
                     - prefix[x1 - 1][y2]
                     - prefix[x2][y1 - 1]
                     + prefix[x1 - 1][y1 - 1];
            sb.append(sum).append('\n');
        }
 
        System.out.print(sb);
    }
}

---

음수 포함 부분합 개수

Map<Long, Long> count = new HashMap<>();
long sum = 0;
long answer = 0;
 
count.put(0L, 1L);
 
for (int x : arr) {
    sum += x;
    answer += count.getOrDefault(sum - k, 0L);
    count.put(sum, count.getOrDefault(sum, 0L) + 1);
}

---

선택 기준

상황	추천
연속 부분합 + 양수	투포인터
연속 부분합 + 음수 포함	누적합 + HashMap
구간합 질의 많음	누적합
2차원 직사각형 합	2차원 누적합
값 추가/변경 + 구간합	Fenwick / Segment Tree

---

백지 복원

1. 음수가 있으면 투포인터가 깨지는 이유는?
2. prefix[r] - prefix[l - 1]이 가능한 인덱스 체계는?
3. 2차원 누적합에서 겹쳐서 빠진 영역을 다시 더하는 항은?