PrefixSum/Interval

1. Prefix Sum (누적합)

• 기본 개념: 누적합을 사용하면 배열의 특정 구간의 합을 O(1) 시간 복잡도로 구할 수 있습니다.

1-1. 1차원 배열에서 Prefix Sum

int[] computePrefixSum(int[] arr) {
    int[] prefixSum = new int[arr.length];
    prefixSum[0] = arr[0];

    for (int i = 1; i < arr.length; i++) {
        prefixSum[i] = prefixSum[i - 1] + arr[i];  // 현재까지의 합 계산
    }

    return prefixSum;
}

// 구간 [l, r]의 합 구하기
int rangeSum(int[] prefixSum, int l, int r) {
    if (l == 0) {
        return prefixSum[r];  // 배열의 처음부터 r까지의 합
    }
    return prefixSum[r] - prefixSum[l - 1];  // 구간 [l, r]의 합
}

1-2. 2차원 배열에서 Prefix Sum (누적합)

int[][] computePrefixSum2D(int[][] arr) {
    int n = arr.length;
    int m = arr[0].length;
    int[][] prefixSum = new int[n][m];

    // 첫 번째 행 및 열 처리
    prefixSum[0][0] = arr[0][0];
    for (int i = 1; i < n; i++) prefixSum[i][0] = prefixSum[i - 1][0] + arr[i][0];
    for (int j = 1; j < m; j++) prefixSum[0][j] = prefixSum[0][j - 1] + arr[0][j];

    // 나머지 행과 열 처리
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            prefixSum[i][j] = arr[i][j] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1];
        }
    }

    return prefixSum;
}

// 2D 구간 [x1, y1]에서 [x2, y2]까지의 합 구하기
int rangeSum2D(int[][] prefixSum, int x1, int y1, int x2, int y2) {
    int result = prefixSum[x2][y2];

    if (x1 > 0) result -= prefixSum[x1 - 1][y2];
    if (y1 > 0) result -= prefixSum[x2][y1 - 1];
    if (x1 > 0 && y1 > 0) result += prefixSum[x1 - 1][y1 - 1];

    return result;
}

---

2. Interval Sum (구간합)

• Segment Tree를 이용해 구간합을 빠르게 구할 수 있습니다.

2-1. Segment Tree를 사용한 구간합

class SegmentTree {
    int[] tree;
    int n;

    public SegmentTree(int[] arr) {
        n = arr.length;
        tree = new int[4 * n];  // 세그먼트 트리 크기
        build(arr, 0, 0, n - 1);
    }

    // 세그먼트 트리 빌드
    private void build(int[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2 * node + 1, start, mid);
            build(arr, 2 * node + 2, mid + 1, end);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

    // 구간합 쿼리
    public int rangeSum(int l, int r) {
        return query(0, 0, n - 1, l, r);
    }

    private int query(int node, int start, int end, int l, int r) {
        if (r < start || l > end) {
            return 0;  // 범위를 벗어난 경우
        }
        if (l <= start && end <= r) {
            return tree[node];  // 구간 내에 완전히 포함된 경우
        }
        int mid = (start + end) / 2;
        int leftSum = query(2 * node + 1, start, mid, l, r);
        int rightSum = query(2 * node + 2, mid + 1, end, l, r);
        return leftSum + rightSum;
    }

    // 업데이트
    public void update(int index, int value) {
        update(0, 0, n - 1, index, value);
    }

    private void update(int node, int start, int end, int index, int value) {
        if (start == end) {
            tree[node] = value;
        } else {
            int mid = (start + end) / 2;
            if (index <= mid) {
                update(2 * node + 1, start, mid, index, value);
            } else {
                update(2 * node + 2, mid + 1, end, index, value);
            }
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }
}

2-2. Fenwick Tree (Binary Indexed Tree)

• Fenwick Tree는 구간 합 및 업데이트를 O(log n) 시간에 수행할 수 있는 자료 구조입니다.

class FenwickTree {
    int[] bit;
    int n;

    public FenwickTree(int n) {
        this.n = n;
        bit = new int[n + 1];  // 1-based 인덱싱
    }

    // 업데이트
    public void update(int index, int value) {
        for (; index <= n; index += index & -index) {
            bit[index] += value;
        }
    }

    // 구간합 쿼리
    public int prefixSum(int index) {
        int sum = 0;
        for (; index > 0; index -= index & -index) {
            sum += bit[index];
        }
        return sum;
    }

    // 구간합 [l, r]
    public int rangeSum(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }
}