[JAVA] 백준 세그먼트 트리 문제모음

 

 

https://www.acmicpc.net/blog/view/9

세그먼트 트리 (Segment Tree)

이 글을 참고하여 세그먼트 트리를 공부하였습니다

 

 

 

 

2042 구간 합 구하기 - 골드1

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

2042번: 구간 합 구하기

처음 풀어보는 세그먼트 트리!! 기쁘다

 

public class Main {
    static int CHANGE = 1;
    static int SUM = 2;
    static long[] arr;
    static long[] segTree;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=  new StringTokenizer(br.readLine());

        int numCnt = Integer.parseInt(st.nextToken());
        int changeCnt = Integer.parseInt(st.nextToken());
        int sumCnt = Integer.parseInt(st.nextToken());

        arr = new long[numCnt+1];
        for (int i =1; i<=numCnt; i++) {
            arr[i] = Long.parseLong(br.readLine());
        }

        segTree = new long[numCnt*4];
        init(1, numCnt, 1);

        StringBuilder sb = new StringBuilder();
        for (int i =0; i<changeCnt+sumCnt; i++) {
            st = new StringTokenizer(br.readLine());

            int calType = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            long c = Long.parseLong(st.nextToken());

            if (calType == CHANGE) {
                long diff = c - arr[b];
                arr[b] = c;
                change(1, numCnt, 1, b, diff);
            } else if (calType == SUM) { //더하는거면 c는 int임
                sb.append("" + sum(1, numCnt, 1, b, (int)c) + "\n");
            }
        }
        System.out.print(sb);
    }

    private static long sum(int start, int end, int node, int left, int right) {
        if (left > end || right < start) {
            return 0;
        }

        if (left <= start && end <= right) {
            return segTree[node];
        }

        int mid = (start + end)/2;
        return sum(start, mid, node*2, left, right) + sum(mid+1, end, node*2+1, left, right);
    }

    private static void change(int start, int end, int node, int idx, long dif) {
        if (idx < start || idx > end) {
            return;
        }

        segTree[node] += dif;
        if (start == end) {
            return;
        }

        int mid  =(start + end)/2;
        change(start, mid, node*2, idx, dif);
        change(mid+1, end, node*2+1, idx, dif);
    }

    private static long init(int start, int end, int node) {
        if (start == end) {
            segTree[node] = 0L + arr[start];
            return segTree[node];
        }

        int mid = (start + end)/2;

        segTree[node] = init(start, mid, node*2) + init(mid+1, end, node*2 + 1);
        return segTree[node];
    }
}

 

 

 

 

2357 최솟값과 최댓값 - 골드1

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

2357번: 최솟값과 최댓값

• 세그먼트 트리에서 리프노드가 아닌 노드들은 리프노드의 합을 저장한다. 이를 통해 범위의 합을 쉽게 구할 수 있음
• 이를 조금만 활용하면 범위 내의 최솟값과 최댓값을 빠르게 찾을 수 있다
  • 리프노드의 합이 아닌 범위내의 최솟값과 최댓값을 저장하면 되겠다
• minSegmentTree와 maxSegmentTree를 만들어서 찾아내면 되겠다

 

public class Main {
    static int[] arr;
    static int[] maxTree;
    static int[] minTree;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int size = Integer.parseInt(st.nextToken());
        int calNum = Integer.parseInt(st.nextToken());

        arr = new int[size+1];

        for (int i =1; i<=size; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        maxTree = new int[size*4];
        minTree = new int[size*4];
        initMin(1, size, 1);
        initMax(1, size, 1);

        StringBuilder sb = new StringBuilder();
        for (int i =0; i<calNum; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            if (end < start) {
                int tmp = end;
                end = start;
                start = tmp;
            }
            int max = getMax(1, size, 1, start, end);
            int min = getMin(1, size, 1, start, end);
            sb.append(min + " " + max + "\n");
        }

        System.out.println(sb);
    }

    private static int initMax(int start, int end, int node) {
        if (start == end) {
            maxTree[node] = arr[start];
            return arr[start];
        }

        int mid = (start + end) / 2;

        maxTree[node] = Math.max(initMax(start, mid, node*2), initMax(mid+1, end, node*2+1));

        return maxTree[node];
    }

    private static int initMin(int start, int end, int node) {
        if (start == end) {
            minTree[node] = arr[start];
            return arr[start];
        }

        int mid = (start + end) / 2;

        minTree[node] = Math.min(initMin(start, mid, node*2), initMin(mid+1, end, node*2+1));

        return minTree[node];
    }

    private static int getMax(int start, int end, int node, int left, int right) {
        if (left > end || start > right) {
            return 0;
        }

        if (left <= start && end <= right) {
            return maxTree[node];
        }

        int mid = (start + end) / 2;

        return Math.max(getMax(start, mid, node*2, left, right),
                getMax(mid+1, end, node*2+1, left, right));
    }

    private static int getMin(int start, int end, int node, int left, int right) {
        if (left > end || start > right) {
            return Integer.MAX_VALUE;
        }

        if (left <= start && end <= right) {
            return minTree[node];
        }

        int mid = (start + end) / 2;

        return Math.min(getMin(start, mid, node*2, left, right),
                 getMin(mid+1, end, node*2+1, left, right));
    }
}

 

 

 

 

11505 구간 곱 구하기 - 골드1

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

11505번: 구간 곱 구하기

• 구간합, 구간최솟값을 위에서 구해봤다
  • 구간 곱이라고 하면 비슷한 느낌으로 풀 수 있을듯
• 고려해야할 사항은 0이 삽입되는 경우와 0이 변경되는 경우이다
  • +) MOD 연산도 잘 고려해줘야한다
  • 나누기의 경우 페르마 소정리를 이용하는 게 좋다
• 나는 zero를 몇 개 포함하는지 개수를 따로 저장하여 갱신하는 식으로 설정했다

 

public class Main {
    static int CHANGE = 1;
    static int MOD = 1_000_000_007;
    static int[] arr;
    static int[] segTree;
    static int[] zeros;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int count = Integer.parseInt(st.nextToken());
        int changeCnt = Integer.parseInt(st.nextToken());
        int multiplyCnt = Integer.parseInt(st.nextToken());

        arr = new int[count+1];

        for (int i =1; i<=count; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        segTree = new int[count*4];
        zeros = new int[count*4];
        init(1, count, 1);

        StringBuilder sb = new StringBuilder();
        for (int i =0; i<changeCnt + multiplyCnt; i++) {
            st= new StringTokenizer(br.readLine());
            int calType = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            if (calType == CHANGE) {
                int tmp = arr[b];
                arr[b] = c;
                change(1, count, 1, b, c, tmp);
            } else {
                sb.append(multiply(1, count, 1, b, c) + "\n");
            }
        }

        System.out.print(sb);
    }

    private static int multiply(int start, int end, int node, int left, int right) {
        if (right < start || end < left) {
            return 1;
        }

        if (left <= start && end <= right) {
            if (zeros[node] > 0) {
                return 0;
            } else {
                return segTree[node];
            }
        }

        int mid = (start + end)/2;
        return (int)(((long)multiply(start, mid, node *2, left, right) * multiply(mid+1, end, node*2+1, left, right)) % MOD);
    }

    private static void change(int start, int end, int node, int idx, int mul, int divide) {
        if (start > idx || end < idx) {
            return;
        }

        long tmp1;
        if (mul == 0) {
            zeros[node] ++;
            tmp1 = segTree[node];
        } else {
            tmp1 = ((long)segTree[node] * mul) % MOD;
        }

        long tmp2 = 1;
        if (divide == 0) {
            zeros[node]--;
        } else {
            tmp2 = pow(divide, MOD -2) % MOD;
        }

        segTree[node] = (int)((tmp1 * tmp2) % MOD);

        if (start == end)
            return;

        int mid = (start + end)/2;
        change(start, mid, node*2, idx, mul, divide);
        change(mid+1, end, node*2+1, idx, mul, divide);
    }

    static long pow(long num, long exponentiation) {
        if (exponentiation == 1) {
            return num;
        }

        long halfPow = pow(num, exponentiation/2);
        long res = halfPow * halfPow % MOD;
        if (exponentiation % 2 == 1) {
            res = (res* num) % MOD;
        }
        return res;
    }

    private static int[] init(int start, int end, int node) {
        if (start == end) {
            segTree[node] = arr[start];
            int count  =0;
            if (segTree[node] == 0) {
                count++;
            }
            return new int[]{segTree[node], count};
        }

        int mid = (start + end)/2;

        int[] result1 = init(start, mid, node*2);
        int[] result2 = init(mid+1, end, node*2+1);

        long tmp = (long)result1[0] * result2[0];
        segTree[node] = (int)(tmp % MOD);
        if (result1[1] + result2[1] > 0) {
            zeros[node] += result1[1] + result2[1];
        }

        return new int[]{segTree[node], zeros[node]};
    }
}

 

 

• 다른 사람들은 +0이 포함된 경우 아예 리프노드부터 갱신해주는 방법을 사용했다 
• 확실히 시간이 덜 걸리고, 메모리도 덜 잡아먹어서 이 방법이 더 좋은 방법인 것 같다
  • 모듈러연산 필요 x
  • 0 개수 배열 필요 x