백준 2268번 <수들의 합7>

백준 알고리즘 2268번

https://www.acmicpc.net/problem/2268

2268번: 수들의 합 7

---

2268번

N개의 수 A[1], A[2], …, A[N] 이 주어졌을 때, 함수 Sum(i, j)는 A[i] + A[i+1] + … + A[j]를 구하는 함수이다. (i > j일 경우에는 A[j] + A[j+1] + ... + A[i]) A가 주어졌을 때, Sum(i, j)를 구하는 것은 매우 쉬운 문제이다. 이러한 (i, j)가 여러 개 주어졌을 때도 별로 어려운 문제는 아니다.

Sum함수와 더불어 Modify라는 함수를 정의하자. Modify(i, k)를 수행하면 A[i] = k가 되는 함수이다. Sum함수와 Modify 함수의 사용 목록이 주어졌을 때, 이에 해당하는 연산을 하는 프로그램을 작성하시오. 두 함수를 섞어서 사용할 수도 있다.

---

문제 해결

세그먼트 트리를 사용해서 푸는 문제이다. 세그먼트 트리를 연습하려고 선택했다!

 

이 문제에서는 세그먼트 트리를 init 하는 함수가 따로 필요가 없다. 왜냐면 A 배열의 숫자들이 초기에는 모두 0이기 때문이다.

 

따라서 문제에서 필요한 연산인 Sum 함수와 Modify 함수만 만들면 된다.

 

Sum 함수는 query 메소드로, Modify 함수는 modify 메소드로 구현을 진행했다.

 

query(int node, int start, int end, int left, int right)

- 만약 구해야 하는 구간(left-right)이 start와 end에 속하지 않는다면 0을 반환한다.

- 만약 구해야 하는 구간에 속한다면 tree[node] 값을 반환한다.

- 걸쳐져 있다면 왼쪽 구간과 오른쪽 구간을 나눠서 재귀함수로 구한다. 

 

modify(int index, int value)

- value와 index의 현재 숫자의 차이를 구해서 update 메소드를 호출한다.

- index의 현재 숫자를 value로 바꾼다.

 

update(int node, int start, int end, int index, long diff) 

- index가 start-end 구간에 포함되지 않으면 아무것도 바뀌지 않는다.

- start와 end가 같다면 index에 해당하는 숫자의 위치이다. 그렇기 때문에 tree[node]에 diff를 더해준다.

- 왼쪽 구간과 오른쪽 구간을 나눠서 재귀 함수를 호출해서 tree[node]의 값을 새로 구한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.Arrays;

public class BOJ_2268 {
    static int N, M;
    static long[] number, tree;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] inArr = br.readLine().split(" ");
        N = Integer.parseInt(inArr[0]);
        M = Integer.parseInt(inArr[1]);

        number = new long[N];
        int h = (int) Math.ceil(Math.log(N) / Math.log(2));
        int treeSize = (1 << (h + 1));
        tree = new long[treeSize];

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            inArr = br.readLine().split(" ");
            int op = Integer.parseInt(inArr[0]);
            int a = Integer.parseInt(inArr[1]);
            int b = Integer.parseInt(inArr[2]);

            if (op == 0) {
                if (b < a){
                    int temp = b;
                    b = a;
                    a = temp;
                }
                sb.append(query(1, 0, N - 1, a-1, b-1)).append("\n");
            } else {
                modify(a-1, b);
            }
        }

        System.out.println(sb);
    }

    static long query(int node, int start, int end, int left, int right) {
        if (start > right || end < left) return 0;
        if (left <= start && end <= right) return tree[node];
        long lsum = query(2 * node, start, (start + end) / 2, left, right);
        long rsum = query(2 * node + 1, (start + end) / 2 + 1, end, left, right);
        return lsum + rsum;
    }

    static void update(int node, int start, int end, int index, long diff) {
        if (start > index || end < index) return;
        if (start == end) {
            tree[node] += diff;
            return;
        }
        update(2 * node, start, (start+end) / 2 , index, diff);
        update(2*node + 1, (start+end) / 2 + 1, end, index, diff);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    static void modify(int index, int value) {
        long diff = value - number[index];
        number[index] = value;
        update(1, 0, N-1, index, diff);
    }
}

---

결과

---