세그먼트 트리 - genomicrangequery

다량의 연속된 데이터(보통 배열)가 있을 때, 구간의 합, 곱, 최소, 최대값 등을 트리형태로 정의해두어 빠르게 값을 구할 수 있는 알고리즘이다.
https://m.blog.naver.com/ndb796/221282210534
위 링크를 보고 정리하다가 추가로 더하고 뺄 내용이 없어보여서 다 지우고 링크만 남긴다ㅠㅠ

링크: https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/
문제설명:
1. 문자열 S가 들어오는데 이는 위 문제에서 나오는 'dna sequence'이며 A, C, G, T 4개의 캐릭터값으로 구성되어있다. 각각은 1, 2, 3, 4의 값으로 대응된다.
예시에서는 S = CAGCCTA 이렇게 주는데 이는 2132241로 변경이 가능하다.
2. P와 Q배열이 주어진다. 배열의 길이는 동일하며 예를들어 P[0] = 2, Q[0] = 4 가 인풋으로 들어온다면 S[2]부터 S[4]사이 최소값을 구하는 문제이다. 여기서는 GCC, 즉 322이므로 답은 2가된다.
3. P[i]와 Q[i]를 input으로 받으며 각각의 범위에 따라 최소값을 가지는 int[]을 리턴한다.
4. 세그먼트 트리를 활용하여 각각의 노드마다 1,2,3,4 중 구간 내 최소값을 갖도록 한다. update는 필요가 없다

import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int init(int start, int end, int node, int[] tree, int[] modifyValues) {
        if (start == end) {
            return tree[node] = modifyValues[start];
        }
        int mid = (start + end) / 2;
        return tree[node] = Math.min(init(start, mid, node*2, tree, modifyValues), init(mid+1, end, node*2+1, tree, modifyValues));
    }

    public int search(int start, int end, int node, int left, int right, int[] tree, int[] modifyValues) {
        if (left > end || right < start) {
            return 10;
        }
        if (left <= start && end <= right) return tree[node];
        int mid = (start + end) / 2;
        return Math.min(search(start, mid, node*2, left, right, tree, modifyValues), search(mid+1, end, node*2+1, left, right, tree, modifyValues));
    }

    public int[] solution(String S, int[] P, int[] Q) {
        char[] arr = S.toCharArray();
        int[] modifyValues = new int[arr.length];
        int[] tree = new int[modifyValues.length * 4];
        HashMap<Character, Integer> map = new HashMap<>();
        int[] result = new int[P.length];
        map.put('A', 1);
        map.put('C', 2);
        map.put('G', 3);
        map.put('T', 4);
        for (int i = 0; i < arr.length; i++) {
            modifyValues[i] = map.get(arr[i]);
        }
        init(0, arr.length - 1, 1, tree, modifyValues);
        for (int i = 0; i < P.length; i++) {
            result[i] = search(0, arr.length - 1, 1, P[i], Q[i], tree, modifyValues);
        }
        return result;
    }
}